Questions tagged [multi-armed-bandit]
For questions related to the multi-armed bandit (MAB) 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.
31
questions
1
vote
0answers
41 views
Which RL algorithm would be suitable for this multi-dimensional and continuous action space?
Is there an RL approach/algorithm that would be suited for the following kind of problem?
There is a continuous action space with an action value $A_{a,t}$ for each action dimension $a$.
The ...
1
vote
0answers
34 views
UCB-like algorithms: how do you compute the exploration bonus?
My question concerns Stochastic Combinatorial Multiarmed Bandits. More specifically, the algorithm called CombUCB1 presented in this paper. It is a UCB-like algorithm.
Essentially, in each round of ...
2
votes
1answer
56 views
In UCB, is the actual upper bound an upper bound of an one-sided or two-sided confidence interval?
I'm a bit confused about the visualization of the upper bound (following the notation of (c.f. Sutton & Barto (2018))
$$Q_t(a)+C\sqrt{\frac{\mathrm{ln}(t)}{N_t(a)}}$$
In many blog posts about the ...
1
vote
0answers
69 views
How do I learn the value function for a POMDP with a single-step horizon (bandit)?
Consider a POMDP with a finite number of environment states, $|\mathcal{S}| = N$, but the number of belief states is uncountably infinite. The belief state space is the convex hull of an $N$ simplex. ...
5
votes
1answer
216 views
Multi Armed Bandits with large number of arms
I'm dealing with a (stochastic) Multi Armed Bandit (MAB) with a large number of arms.
Consider a pizza machine that produces a pizza depending on an input $i$ (equivalent to an arm). The (finite) set ...
1
vote
0answers
27 views
Multi-armed bandit problem without getting rewards
In a 2-armed-bandit problem, an agent has an opportunity to see n reward for each action. Now the agent should choose actions m times and maximize the expected reward in these m decisions. but it cant ...
2
votes
3answers
78 views
Why aren't exploration techniques, such as UCB or Thompson sampling, used in full RL problems?
Why aren't exploration techniques, such as UCB or Thompson sampling, typically used in bandit problems, used in full RL problems?
Monte Carlo Tree Search may use the above-mentioned methods in its ...
1
vote
0answers
29 views
Multi-armed bandits: reducing stochastic multi-armed bandits to bernoulli bandits
Agrawal and Goyal (http://proceedings.mlr.press/v23/agrawal12/agrawal12.pdf page 3) discussed how we can extend Thompson sampling for bernoulli bandits to Thompson sampling for stochastic bandits in ...
2
votes
1answer
111 views
Why do we have two similar action selection strategies for UCB1?
In the literature, there are at least two action selection strategies associated with the UCB1's action selection strategy/policy. For example, in the paper Algorithms for the multi-armed bandit ...
3
votes
2answers
100 views
Why is regret so defined in MABs?
Consider a multi-armed bandit(MAB). There are $k$ arms, with reward distributions $R_i$ where $1 \leq i \leq k$. Let $\mu_i$ denote the mean of the $i^{th}$ distribution.
If we run the multi-armed ...
3
votes
0answers
20 views
Mapping given probabilities to empirical probabilities
Consider following problem statement:
You have given $n$ actions. You can perform any of them. Each action gives you success with some probability. The challenge is to perform given finite number of ...
2
votes
0answers
25 views
Is there a UCB type algorithm for linear stochastic bandit with lasso regression?
Why is there no upper confidence bound algorithm for linear stochastic bandits that uses lasso regression in the case that the regression parameters are sparse in the features?
In particular, I don't ...
1
vote
1answer
82 views
Understanding GLIE conditions for epsilon greedy approach
I was going through this course on reinforcement learning (the course has two lecture videos and corresponding slides) and I had a doubt. On slide 18 of this pdf, it states following condition for an ...
4
votes
1answer
72 views
Can you convert a MDP problem to a Contextual Multi-Arm Bandits problem?
I'm trying to get a better understanding of Multi-Arm Bandits, Contextual Multi-Arm Bandits and Markov Decision Process.
Basically, Multi-Arm Bandits is a special case of Contextual Multi-Arm Bandits ...
1
vote
0answers
29 views
Customized food for persons based on their profile using Reinforcement learning
I am newbie to Reinforcement Learning, this is my idea - Agent(food provider) has to select a food based on the environment(based on the user profile). Here the reward will be given to the agent based ...
4
votes
2answers
110 views
Why do we use $X_{I_t,t}$ and $v_{I_t}$ to denote the reward received and the at time step $t$ and the distribution of the chosen arm $I_t$?
I'm doing some introductory research on classical (stochastic) MABs. However, I'm a little confused about the common notation (e.g. in the popular paper of Auer (2002) or Bubeck and Cesa-Bianchi (2012)...
1
vote
0answers
39 views
Solving multi-armed bandit problems with continuous action space
My problem has a single state and an infinite amount of actions on a certain interval (0,1). After quite some time of googling I found a few paper about an algorithm called zooming algorithm which can ...
0
votes
0answers
31 views
Is there a multi-agent version of EXP3?
The EXP3 algorithm as given in the figure below (taken from Adversarial Bandits and the Exp3 Algorithm) is to solve the adversarial bandits for the single-player case.
What happens if there are ...
0
votes
1answer
203 views
Why am I getting better performance with Thompson sampling than with UCB or $\epsilon$-greedy in a multi-armed bandit problem? [closed]
I ran a test using 3 strategies for multi-armed bandit: UCB, $\epsilon$-greedy, and Thompson sampling.
The results for the rewards I got are as follows:
Thompson sampling had the highest average ...
5
votes
1answer
194 views
How do I recognise a bandit problem?
I'm having difficulty understanding the distinction between a bandit problem and a non-bandit problem.
An example of the bandit problem is an agent playing $n$ slot machines with the goal of ...
1
vote
1answer
62 views
When discounted MAB is useful?
Many of multi-armed bandit(MAB) algorithms are used when the total reward is the sum of all rewards. However, in RL, the discounted reward is mainly used. Why is the discounted reward not prevailing ...
3
votes
2answers
119 views
Are bandits considered an RL approach?
If a research paper uses multi-armed bandits (either in their standard or contextual form) to solve a particular task, can we say that they solved this task using a reinforcement learning approach? Or ...
1
vote
1answer
61 views
How do we reach at the formula for UCB action-selection in multi-armed bandit problem?
I came across the formula for Upper Confidence Bound Action Selection (while studying multi-armed bandit problem), which looks like:
$$
A_t \dot{=} \operatorname{argmax}_a \left[ Q_t(a) + c \sqrt{ \...
1
vote
0answers
37 views
How do I determine the optimal policy in a bandit problem with missing contexts?
Suppose I learn an optimal policy $\pi(a|c)$ for a contextual multi-armed bandit problem, where the context $c$ is a composite of multiple context variables $c = c_1, c_2, c_3$. For example, the ...
2
votes
1answer
122 views
Solving a Multi-Armed, “Multi-Bandit” Problem
This is the problem: I have 66 slot-machines and for each of them I have 7 possible actions/arms to choose from. At each trial, I have to choose one of 7 actions for each and every one of the 66 slots....
5
votes
1answer
188 views
It is possible to solve a problem with continuous action spaces and no states with reinforcement learning?
I want to use Reinforcement Learning to optimize the distribution of energy for a peak shaving problem given by a thermodynamical simulation. However, I am not sure how to proceed as the action space ...
2
votes
1answer
444 views
How to implement a contextual reinforcement learning model?
In a reinforcement learning model, states depend on the previous actions chosen. In the case in which some of the states -but not all- are fully independent of the actions -but still obviously ...
1
vote
1answer
282 views
How can I incorporate domain knowledge to choose actions in the case of large action spaces in multi-armed bandits?
Suppose one is using a multi-armed bandit, and one has relatively few "pulls" (i.e. timesteps) relative to the action set. For example, maybe there are 200 timesteps and 100 possible actions....
1
vote
0answers
32 views
Name of a multiarmed bandit with only some levers available
In order to model a card game, as an exercise, I was thinking of an elementary setting as a multiarmed bandit, each lever being the distribution of expected rewards of a specific card.
But, of course,...
2
votes
1answer
65 views
Programming a bandit to optimize donations
I'm developing a multi-armed bandit which learns the best information to display to persuade someone to donate to charity.
Suppose I have treatments A, B, C, D (which are each one paragraph of text). ...
5
votes
1answer
201 views
What is a weighted average in a non-stationary k-armed bandit problem?
In the book Reinforcement Learning: An Introduction (page 25), by Richard S. Sutton and Andrew G. Barto, there is a discussion of the k-armed bandit problem, where the expected reward from the bandits ...