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

64 questions
Filter by
Sorted by
Tagged with
79 views

### What reinforcement learning algorithm should I use for the following problem?

Environment I have a static timeseries environment meaning the environment is the same. This problem is a multi armed bandit problem. Time t0 t1 t2 State s0 s1 s2 Score 10 0.1 0.2 Class 1 0 0 ...
32 views

### Can we use MAB in problems that reset after some time?

I have this scheduling problem. There are $n$ jobs, one machine and $T$ time slots. To be satisfied, each job $i=1,\ldots,n$ must receive at least the quantity $v_i$ from the machine. The machine can ...
1 vote
104 views

### References on Theoretical Bandit Problem

I am going to start learning the bandit problem and algorithm, especially how to bound the regret. I found the book Bandit Algorithms'' but it is not easy to follow. It is based on advanced ...
1 vote
63 views

### Python libraries for mulit-armed bandit problems [closed]

I am working on a problem that can be casted as a contextual bandit problem with continuous action space. I would like to tackle it by using something like the contextual zooming algorithm from the ...
64 views

### Is it possible to describe wordle as a multi armed bandit problem?

Game wordle got fame in January 2022 on Twitter (now knows as X). Rules are pretty simple. Player has to guess a word of length 5 Player can make at most 6 guesses ...
1 vote
66 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 ...
47 views

### Where can I find good sources (textbook, lecture notes, etc) on multi-armed bandits?

I am looking for good sources (textbook, lecture notes, etc) on multi-armed bandits where both theory and practical examples are given. I will be happy for suggestion of such material.
64 views

### Optimal sensor placement formulation as multi-armed bandit [closed]

Assume that I have $n$ sensors to be placed optimally in $N$ possible locations where $n<<N$. How can I model this problem as a multi-armed bandit problem?
7k 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 ...
25 views

### Can RL solve scheduling problems with unknown function

I have the following scheduling problem. There are $n$ tasks and $m>n$ machines. Each task $i$ has a requirement $t_i$ that should be guaranteed. Any task can be scheduled on at least one machine ...
16 views

### Do Bernoulli bandits need a different treatment if the rewards are sparse?

I have a problem where, effectively, my slot machines have very low payout probability (on the order of 1% for the "best" slot machines) and my goal is to minimize the number of actions to ...
78 views

### UCB, Thompson sampling etc seems myopic/greedy for bandits?

When considering multi-armed bandits in different formats, UCB, $\epsilon$-greedy, thompson sampling etc seems so greedy/myopic in the sense that it solely considers reward for the current timestep. ...
31 views

### The impact of allowing the reward to be negative in a contextual bandit problem

I posted this question on stats.stackexchange.com 3 days ago. But there has been no answer. I would like to try my luck here. It seems the contextual bandits problems, as shown in these two papers ...
21 views

### Finding an optimal action score function for Multi-Armed Bandit Problem

Considering a multi-armed bandit problem where there are : ...
1 vote
114 views

### Is it true that a multi-armed-bandit selects an action based on the future reward?

During my machine learning lecture I saw the following statement on the slides: "Multi-armed-bandit selects an action based on the future reward" Is that statement true? In my opinion it is ...
552 views

### Should I use multi-armed-bandits or RL for a financial time-series problem?

If we take simple financial timeseries data(stock/commodity/currency prices), State(t+1) does not depend on the action that we choose to take at State(t) as in Maze or Chess problem. Simple example: ...
1 vote
55 views

### Why will every action be sampled an infinite number of times?

I am reading the book Reinforcement Learning: An Introduction. Second edition (Richard S. Sutton and Andrew G. Barto). In the k-armed bandit problem using $\varepsilon$-greedy selection method, the ...
188 views

### Is there a way to form a reward function so that it would take into account the order of the actions?

I want to design a multi-arm bandit system for a multi-step, multi-location system. Locations are dynamic, so I can not design the system based on them. In each location, the alternative actions that ...
1 vote
50 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/...
52 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 ...
1 vote
65 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 ...
228 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$?
1 vote
87 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 ...
56 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 ...
77 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 (...
99 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 ...
876 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
571 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 ...
1 vote
113 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-...
131 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 ...
1 vote
58 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 ...
349 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 ...
1 vote
125 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'...
738 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$, ...
4k 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$...
601 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 ...
1 vote
202 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 ...
1 vote
104 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
824 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 ...
726 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 ...
796 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 ...
1 vote
246 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 ...
496 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
98 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. ...
1 vote
351 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....
1k 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 ...
120 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)...
380 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 ...