# 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.

140 questions
Filter by
Sorted by
Tagged with
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 ...
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, ...
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 ...
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 ...
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 ...
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 ...
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?
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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-...
2k views

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 ...
330 views

### Thompson Sampling

I read on Wikipedia that Thompson sampling consists in playing the action $a \in {\mathcal {A}}$ according to the probability that this action maximizes the expected reward. This ...
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. ...
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- or N-armed bandit problem) is the problem a gambler faces at a ...
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 ...
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 ...
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 ...
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 ...
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 ...
323 views

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 ...
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 ...
150 views

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 ...
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 ...
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, ...
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 ...
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 ...
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 ...
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 ...
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 ...
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....