Questions tagged [multi-armed-bandits]

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.

Filter by
Sorted by
Tagged with
0 votes
0 answers
7 views

Data Imbalance in Contextual Bandit with Thompson Sampling

I'm working with the Online Logistic Regression Algorithm (Algorithm 3) of Chapelle and Li in their paper, "An Empirical Evaluation of Thompson Sampling" (https://papers.nips.cc/paper/2011/...
user avatar
  • 1
0 votes
0 answers
28 views

How to model the probability of click-through in bandit problem?

Consider a bandit problem in which we want to maximize the probability of click-through based on bid values ($b$ is the value of bid and $\Pr(b)$ shows the probability that a customer clicks on a link ...
user avatar
  • 451
1 vote
0 answers
41 views

Policy gradient (or more general, RL algorithms) for the problems where actions does not determine next state (next state is independent to action)

I am pretty new in RL. Could anyone suggest results/paper about whether or not policy gradient (or more general RL algorithms) can be applied to the problems where actions does not determine next ...
user avatar
  • 11
1 vote
1 answer
20 views

If the probabilities with which each task is selected for you do not change over time, why would it appear as a single stationary k-armed bandit task?

Sutton-Barto (Section 2.9-Associative Search (Contextual Bandits), page 41): As an example, suppose there are several different k-armed bandit tasks, and that on each step you confront one of these ...
user avatar
1 vote
1 answer
35 views

Gradient bandit algorithm: is $\bar{R}_t$ average of all rewards or average of rewards corresponding to $A_t$?

Sutton-Barto (Section 2.8-Gradient Bandit Algorithms, page 37): Question: is $\bar{R}_t$ average of all rewards or average of rewards corresponding to $A_t$?
user avatar
1 vote
0 answers
26 views

Can vanilla multi armed bandit problems be solved by RL algorithms like A2C and PPO?

Let's say we have N bandit machines with some distributions (assume some are gaussian, some are uniform, some are chi squared). We want to maximize rewards in X amount of time. I am aware that ...
user avatar
0 votes
0 answers
26 views

Will adding new arms after every time step still make the problem a Multi Armed Bandit problem?

In Multi Armed Bandit problem, let's say I have 4 arms- {S1, S2, S3, S4}. Each arm has their own probability distribution of rewards. I play the first arm (S1); I get +2 as reward. I add 2 more arms ...
user avatar
0 votes
0 answers
35 views

Is there a variant of Thompson Sampling that works with variable bandits?

Does there exist a variant of TS, such that, while computing the returns of multi-armed bandits, we have the possibility of introducing an extra bandit? For instance, while we are applying TS to 3 ...
user avatar
0 votes
0 answers
66 views

Are Best-Arm Bandits considered to be reinforcement learning?

Multi Armed Bandits (MABs) are a broad field of research pursuing different streams. In addition to the common objective of maximizing the cumulative reward, there are also so-called Best-Arm (...
user avatar
  • 101
0 votes
0 answers
44 views

Which algorithms work in a non-stationary stochastic environment?

Currently, I am reading into the Multi-Armed-Bandit problem and found the special case of non-stationary (environment and its attributes, like the reward distribution, change over time) stochastic ...
user avatar
0 votes
0 answers
27 views

What is the role of the observation in the standard Multi-Armed-Bandit?

I'm trying to understand how to model the environment for a MAB problem. I'm following the TensorFlow tutorial on it. In the Introduction and Environment chapter is stated: agents do not model state ...
user avatar
1 vote
0 answers
33 views

Is there a paper/article on contextual $\epsilon$-greedy algorithm?

I am reading the paper A Contextual-Bandit Approach to Personalized News Article Recommendation, where it refers to $\epsilon$-greedy (disjoint) algorithm. I suspect, that it is just a version of a K-...
user avatar
  • 223
0 votes
0 answers
34 views

Why does the Bandit Slippery Walk environment have complimentary probabilities?

I am learning about Reinforcement learning in the book Grokking Deep Reinforcement Learning. Below are snippets. Below is the description of Bandit Slippery Walk (BSW) Below is the description of two ...
user avatar
1 vote
0 answers
37 views

Multi-armed Bandit in optimization on graph edges selection

I have the problem, which I described below. I wonder if there exists a class of multi-armed bandit approaches that is related to it. I am working on computer networking optimization. In the simplest ...
user avatar
  • 21
2 votes
0 answers
47 views

Is it better to model a Contextual Multi-Armed Bandit problem as an MDP with a non-zero discount factor than treating it as it is?

I'd like to ask if it is, generally, better to model a problem that naturally appears as a Contextual Multi-Armed Bandit like Recommender Systems as a Markov Decision Process with a non-zero discount ...
user avatar
  • 509
1 vote
1 answer
76 views

Why do I get bad results no matter my neural network function approximator for parametrized Q-learning implementation for Contextual Bandits?

I'd like to ask you why, no matter my neural network function approximator for parametrized Q-learning implementation for a Contextual Bandits environment, I'm getting bad results. I don't know if it'...
user avatar
  • 509
3 votes
1 answer
221 views

Is the Bandit Problem an MDP?

I've read Sutton and Barto's introductory RL book. They define a policy as a mapping from states to probabilities of selecting each possible action. If the agent is following policy $\pi$ at time $t$, ...
user avatar
  • 203
5 votes
1 answer
891 views

What is the probability of selecting the greedy action in a 0.5-greedy selection method for the 2-armed bandit problem?

I'm new to reinforcement learning and I'm going through Sutton and Barto. Exercise 2.1 states the following: In $\varepsilon$-greedy action selection, for the case of two actions and $\varepsilon=0.5$...
user avatar
  • 509
4 votes
1 answer
992 views

What are the major differences between multi-armed bandits and the other well-known algorithms (DQN, A3C, PPO, etc)?

I have studied in the past different algorithms, i.e. DQN, DDQN, REINFORCE, A3C, PPO, TRPO, so on. I am doing an internship this summer where I have to use a multi-armed bandit (MAB). I am a bit ...
user avatar
2 votes
1 answer
152 views

Difference in UCB performance when scaling the rewards

I notice the following behavior when running experiments with $\epsilon$-greedy and UCB1. If the reward is kept binary (0 or 1) both algorithm's performances are on par with each other. However, if I ...
user avatar
  • 223
1 vote
0 answers
67 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 ...
user avatar
  • 11
1 vote
0 answers
87 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 ...
user avatar
  • 11
2 votes
1 answer
153 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 ...
user avatar
  • 101
1 vote
0 answers
79 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. ...
user avatar
  • 61
5 votes
1 answer
397 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 ...
user avatar
  • 101
1 vote
0 answers
35 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 ...
user avatar
  • 111
3 votes
3 answers
142 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 ...
user avatar
  • 167
1 vote
0 answers
34 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 ...
user avatar
  • 287
4 votes
1 answer
211 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 ...
user avatar
  • 33.8k
4 votes
2 answers
266 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 ...
user avatar
3 votes
0 answers
26 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 ...
user avatar
  • 211
2 votes
0 answers
35 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 ...
user avatar
  • 21
1 vote
0 answers
284 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 ...
user avatar
  • 131
4 votes
1 answer
441 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 ...
user avatar
  • 141
1 vote
0 answers
30 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 ...
user avatar
  • 11
4 votes
2 answers
114 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)...
user avatar
2 votes
0 answers
82 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 ...
user avatar
  • 21
0 votes
1 answer
1k 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 ...
user avatar
5 votes
1 answer
223 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 ...
user avatar
  • 295
1 vote
1 answer
92 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 ...
user avatar
  • 451
5 votes
2 answers
569 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 ...
user avatar
1 vote
1 answer
145 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{ \...
user avatar
1 vote
0 answers
43 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 ...
user avatar
2 votes
1 answer
186 views

Which solutions could I use to solve a multi-armed "multi-bandit" problem?

Problem I have 66 slot machines. 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. The reward ...
user avatar
  • 145
5 votes
1 answer
303 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 ...
user avatar
  • 145
2 votes
1 answer
502 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 ...
user avatar
  • 236
1 vote
1 answer
512 views

Why is it useful in some applications to use features that are shared by all arms?

In Li et al. (2010)'s highly cited paper, they talk about LinUCB with hybrid linear models in Section 3.2. They motivate this by saying In many applications including ours, it is helpful to use ...
user avatar
  • 153
1 vote
1 answer
310 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....
user avatar
  • 153
1 vote
0 answers
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,...
user avatar
  • 51
2 votes
1 answer
77 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). ...
user avatar
  • 153