Questions tagged [multiarmed-bandit]

A problem in which a fixed limited set of resources must be allocated between competing (alternative) choices in a way that maximizes their expected gain, when each choice's properties are only partially known at the time of allocation.

Filter by
Sorted by
Tagged with
30
votes
3answers
8k views

Best bandit algorithm?

The most well-known bandit algorithm is upper confidence bound (UCB) which popularized this class of algorithms. Since then I presume there are now better algorithms. What is the current best ...
15
votes
4answers
2k views

In what kind of real-life situations can we use a multi-arm bandit algorithm?

Multi-arm bandits work well in situation where you have choices and you are not sure which one will maximize your well being. You can use the algorithm for some real life situations. As an example, ...
14
votes
2answers
4k views

What is Thompson Sampling in layman's terms?

I am unable to understand Thompson Sampling and how it works. I was reading about Multi Arm Bandit and after reading Upper Confidence Bound Algorithm, many text suggested that Thompson Sampling ...
14
votes
1answer
1k views

Cost functions for contextual bandits

I'm using vowpal wabbit to solve a contextual-bandit problem. I'm showing ads to users, and I have a fair bit of information about the context in which the ad is shown (e.g. who the user is, what ...
13
votes
1answer
2k views

Optimal algorithm for solving n-armed bandit problems?

I've read about a number of algorithms for solving n-armed bandit problems like $\epsilon$-greedy, softmax, and UCB1, but I'm having some trouble sorting through what approach is best for minimizing ...
11
votes
1answer
2k views

Multi armed bandit for general reward distribution

I'm working on a multi-armed bandit problem where we do not have any information about the reward distribution. I have found many papers which guarantee regret bounds for a distribution with known ...
8
votes
2answers
424 views

Etymology of multi-armed bandit

I'm studying Reinforcement Learning, and have come across multi-armed bandits. Why are these called bandits? And why are they armed?
8
votes
2answers
5k views

Upper Confidence Bound in Machine Learning

I came across the formula for obtaining the upper confidence bounds on the k-armed bandit problem: $$c\sqrt{\frac{\text{ln} N_i}{n_i}}$$ where $n_i$ is the amount of samples we have for this ...
7
votes
3answers
477 views

Multi-armed bandit algorithms vs Uplift modeling

Multi-Armed Bandit: http://en.wikipedia.org/wiki/Multi-armed_bandit Uplift Modeling: http://en.wikipedia.org/wiki/Uplift_modelling How are these two approaches different? How are they similar? Is ...
6
votes
0answers
240 views

Bandits with mixed reward processes?

I am trying to model a sequential exploration-exploitation problem with learning as a multi-armed bandit, where the reward mixes a Markovian and a stochastic reward. I understand how to model a ...
5
votes
2answers
2k views

Can sub-Gaussian distributions have non-zero mean?

A random variable $X$ is sub-Gaussian if there exists a $b>0$ such that for all $t \in \mathbb{R}$ we have $$\mathbb{E}(\exp(tX)) \leq \exp(b^2t^2/2).$$ According to some sources online such as ...
5
votes
2answers
930 views

A continuous generalization of the binary bandit

There is plenty of reading out there about Bayesian (beta-binomial) multiarm bandits for 0/1 data, but I would like to extend this slightly. To give some context, suppose I have two webpages, A and ...
4
votes
2answers
4k views

Linear Regret for epsilon-greedy algorithm in Multi-Armed Bandit problem

I am reading about $\epsilon$-greedy algorithm in Multi-Armed Bandit (or $K$ armed bandit) problem, as can be seen here: https://en.wikipedia.org/wiki/Multi-armed_bandit#Semi-uniform_strategies. For ...
4
votes
2answers
43 views

What is the relationship between Boltzmann / Gibbs sampling and the softmax function?

I'm looking at sampling functions in the context of reinforcement learning; specifically the explore/exploit problem. A method I've seen pretty often is to derive the action by assigning a score to ...
4
votes
1answer
1k views

Thomson/Bayesian Bandit Algorithm

I am looking to use the Bayesian Bandits Strategy to find the best arm of a Multi armed bandit. As outlined in the link, the Bayesian algorithm is Sample a random variable $X_b$ from the prior of ...
4
votes
1answer
438 views

multi-armed bandit with seasonality

I'm working on implementing a multi-armed-bandit-like approach for determining the best price to offer for a product. Our goal is to optimize profit, meaning, we want to find the price where (price-...
4
votes
1answer
2k views

Gradient Bandit Algorithm baseline

I am reading Sutton's latest draft of "Reinforcement learning, an introduction" and I came to the Gradient Bandit Algorithm (page 29). I am having a bit of trouble understanding how the baseline ...
4
votes
1answer
330 views

Thompson Sampling

I read on Wikipedia that Thompson sampling consists in playing the action ${\displaystyle a \in {\mathcal {A}}}$ according to the probability that this action maximizes the expected reward. This ...
4
votes
2answers
71 views

Sampling procedure to find distribution of maximal mean (pure exploration no exploitation)

Given n distributions with unknown means, what finite sampling procedure could maximize the probability of finding the distribution with the highest mean? More elaborately: I have n sacks of coins. ...
4
votes
1answer
2k views

Multi-armed bandit algorithms in Java?

Multi-armed_bandit problem defenition from Wikipeda: "In probability theory, the multi-armed bandit problem (sometimes called the K-[1] or N-armed bandit problem) is the problem a gambler faces at a ...
4
votes
1answer
539 views

How to test if bandit algorithm is converging?

I have coded up the a multi-armed bandit algorithm based on algorithm 1 in the original LinUCB algorithm paper, but I am having trouble determining if it is working properly. My test setup is the ...
4
votes
1answer
4k views

Multi Armed Bandit for Continuous Rewards - Extended Question

This question is an extension to A continuous generalization of the binary bandit The Multi-Armed Bandit (MAB) Problem in general is described here: https://en.wikipedia.org/wiki/Multi-armed_bandit ...
4
votes
2answers
311 views

Why UCB algorithm (of multi armed bandit) gives i.i.d. reward sequence?

I am reading the proofs of regrets bounds of UCB algorithms, and find the following thing quite confusing. Suppose $T_i(t)$ is the number of times pulling arm $i$, and $I_i(t)$ is set of stages ...
4
votes
1answer
987 views

Gaussian Multi-Armed Bandits and the UCB Algorithm

I've implemented in MATLAB the UCB algorithm for gaussian bandits with zero mean and unit variance (these means were themselves sampled from a gaussian prior of zero mean and unit variance). Now I ...
4
votes
0answers
309 views

Multi armed bandits with known reward estimates

Consider a bandit problem in which you know the set of expected payoffs for pulling various arms, but you do not know which arm maps to which expected payoff. Can you design a regret minimizing ...
4
votes
0answers
323 views

Optimal Stopping for Bernoulli One-Armed Bandit with a Fixed, Known Payout

I'm very new to bandit problems (apologies if I've formatted my question incorrectly), but I have to solve the optimal stopping of what I think is a very simple case. Suppose I have two arms $k = {1, ...
3
votes
1answer
289 views

Q-Learning: state independent of agent's action [closed]

Could state be independent of the action chosen by agent? We would have a situation in which agent learns only which actions are the best in specific states without having any impact on those states (...
3
votes
1answer
64 views

Minor confusion over Thompson sampling

On a paper concerning Thompson sampling (TS) I found a quote: In order to exploit the estimated uncertainties, TS dedicates a higher chance to explore an action if its uncertainty increases. ...
3
votes
2answers
235 views

Multi Armed Bandit Augmented With Machine Learning Priors

Suppose we have a list of items $I_1,\cdots,I_K$, and we would like to order them by popularity using a Multi Armed Bandit approach. As a concrete example, imagine we're trying to advertise a toy on ...
3
votes
1answer
356 views

Multi-armed bandit in face of full reward information

I am new to this area of machine learning. I am just walking myself through UCB1 algorithm which seems to assume that the payoff can be learnt only for action that ...
3
votes
1answer
20 views

A small adjustment to the Multi-Armed Bandit problem

What class of problems does this belong to: Similar to multi-armed bandit, but with a small adjustment/difference: by choosing an action at every time step you not only receive the reward of that ...
3
votes
1answer
63 views

Calculating payout of strategy for two one-armed bandits

I am trying to calculate the expected payout of the following strategy: You have two one-armed bandits: one pays out \$$1$ with probability $0.4$, the other pays out \$$1$ with probability $0.5$, you ...
3
votes
1answer
173 views

Maximum Multi-armed Bandit

My problem is similar to the multi-armed bandit problem in that I need to allocate "pulls" between n options, each giving a stochastic real reward and the pulls for ...
3
votes
1answer
57 views

What does this logarithmic decay schedule mean?

In the context of minimizing regret among $\varepsilon$-greedy strategies for a multi-armed bandit problem, a number of sources* present the following decay schedule with a claim that it has ...
3
votes
0answers
150 views

Thompson sampling with adaptive kernel density estimation

This is an extension to this question, which is about handling arbitrary (potentially unbounded) reward distributions for the multi-armed bandit problem. Given a sequence of observed rewards $r_t \in \...
3
votes
0answers
89 views

Regret Minimization with Hidden Markov Processes

Consider a hidden Markov process with two states $\{0, 1\}$ represented with $Z_t$. The transition matrix is unknown, although we can assume it's strongly diagonal (i.e. slow-switching). At any time, ...
3
votes
2answers
415 views

Exploiting features in a multiarmed bandit scenario

I am facing a challenging problem: Say I have shirts of three different colors (same price). And say I am running a strange kind of store in into which people come in one by one, and I can show ...
2
votes
2answers
1k views

Multi-armed bandit vs AB testing

I'm trying to understand the difference between AB Testing and Multi armed bandit and when we should use one of the other. It seems to me that Multi-armed bandit algorithms are statistically valid and ...
2
votes
1answer
254 views

For a Multi-arm Bandits set-up, does the Signal to Noise Ratio have any meaning there?

Suppose that we have a Multi-arm Bandit set-up with $K = 5$ bandits. Each bandit has a reward distribution of: $$ X_i \sim Bern(p_i), \ \ \ i \in \{1, \ldots, 5\} $$ In literature about MABs, ...
2
votes
1answer
237 views

Are there frequentist approaches to Thompson Sampling?

What is the theoretical reason why Thompson Sampling needs to involve posterior distributions? Why can we not sample over predictive distributions? (or is the issue that predictive frequentist ...
2
votes
1answer
306 views

Multi armed bandit algorithms failing with un-scaled rewards

I am experimenting with the multi-armed bandit algorithms (namely: epsilon greedy, decaying epsilon greedy, optimistic initial value, upper confidence interval, and Thompson sampling). My reward is ...
2
votes
1answer
1k views

UCB1 for Multi Armed Bandit is stochastic or deterministic?

I would like to know if UCB1 for multi armed bandit problems is deterministic or stochastic. I understand that the arm chosen depends on the expected reward and the "width" of the upper bound, ...
2
votes
2answers
93 views

Multiarmed-bandit problem, why can't we use brute force method to tackle this problem

since in multiarmed-bandit problem, we can choose which arm to take and get the corresponding reward, however, why can't we conduct a lot of choice of each arm and estimate their probabilities of the ...
2
votes
2answers
1k views

Weird results of Q-learning with Softmax

I am implementing an N-armed-bandit with Q-learning. This bandit uses Softmax as its action selection strategy. This bandit can choose between 4 arms, of which the rewards are distributed as a ...
2
votes
2answers
866 views

Why is this regret a good choice for a multi-armed bandit?

The regret in a multi-arm bandit model is given by $$\underset{j}{\max}\sum_{t=1}^{T}x_j(t) -G_{A}$$ where $$G_A=\sum_{t=1}^{T}x_{it}(t)$$ is the total reward achieved by the learner, based on an ...
2
votes
1answer
66 views

What is the best strategy for the simplified version of the multi-armed bandit?

Consider a simplified version of the multi-armed bandit problem, where: like in the standard multi-armed bandit: when you pull the lever of 1 bandit you win/lose some amount from that bandit ...
2
votes
1answer
40 views

States in Bandit Problems

I am wondering if there is an interpretation of the Bandit Problem with more than one states. I know that there are versions which views each slot machine as an independent Markovian machines and as ...
2
votes
2answers
72 views

Contextual bandits: Number of models to estimate

I have recently read several papers on contextual bandits especially for the case of binary rewards. However, one very basic aspect is not entirely clear to me: In some papers (e.g. here https://arxiv....
2
votes
1answer
334 views

UCB Exploration in Reinforcement Learning

I have two questions regarding the upper confidence bounds (UCB) exploration in reinforcement learning: UCB exploration is derived from Hoeffding's inequality which assumes that the reward is bounded ...
2
votes
1answer
113 views

Using IPS(inverse probability weighting) with a deterministic policy as the logging policy

In a contextual bandit problem, why can't we use inverse probability weighting (inverse propensity score) with a deterministic policy as the logging policy? Could you give me a concrete example?