Skip to main content
Share Your Experience: Take the 2024 Developer Survey
12 votes
Accepted

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

You should start with the general definition of Reinforcement Learning problem. And what Markov Decision Process is. DQN, A3C, PPO and REINFORCE are algorithms for solving reinforcement learning ...
Kostya's user avatar
  • 2,534
6 votes
Accepted

Are bandits considered an RL approach?

Several important researchers distinguish between bandit problems and the general reinforcement learning problem. The book Reinforcement learning: an introduction by Sutton and Barto describes bandit ...
nbro's user avatar
  • 40.8k
5 votes
Accepted

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

I read section 2.2 of Sutton and Barto, and I understand your confusion: the $\epsilon$-greedy algorithm is not defined precisely on page 27-28. Selecting an action randomly "every once in awhile&...
DeepQZero's user avatar
  • 1,399
5 votes

How to implement a contextual reinforcement learning model?

In the case in which some of the states -but not all- are fully independent of the actions -but still obviously determine the optimal actions-, how could we take these state variables into account? I ...
Neil Slater's user avatar
  • 32.4k
4 votes
Accepted

How do I recognise a bandit problem?

The bandit problem has one state, in which you are allowed to choose one lever among $n$ levers to pull. Why is there just one state in the formulation of this bandit problem? There is one state ...
DeepQZero's user avatar
  • 1,399
4 votes
Accepted

Why aren't exploration techniques, such as UCB or Thompson sampling, used in full RL problems?

You can indeed use UCB in the RL setting. See e.g. section 38.5 Upper Confidence Bounds for Reinforcement Learning (page 521) of the book Bandit Algorithms by Csaba Szepesvari and Tor Lattimore for ...
nbro's user avatar
  • 40.8k
4 votes
Accepted

Why is regret so defined in MABs?

In short, you don't regret your bad luck that you could do nothing about, you regret your bad choices that you could have done something about if only you knew. The point of regret as a metric ...
Neil Slater's user avatar
  • 32.4k
4 votes

Can you convert a MDP problem to a Contextual Multi-Arm Bandits problem?

The main difference between an MDP and contextual bandit setting is time steps and state progression. If those are important to the problem you want to solve, then it is not possible to convert. ...
Neil Slater's user avatar
  • 32.4k
3 votes

Why aren't exploration techniques, such as UCB or Thompson sampling, used in full RL problems?

Many techniques for the exploration/exploitation dilemma that are inspired by multi-armed bandit problems, such as UCB1, assume that you can explicitly enumerate all state-action pairs; in fact, multi-...
Dennis Soemers's user avatar
  • 10.3k
3 votes

Why am I getting better performance with Thompson sampling than with UCB or $\epsilon$-greedy in a multi-armed bandit problem?

The first thing to note here is that your results seem aligned with the results commonly found in the bandit literature. Second thing to note would be that the performance of bandit algorithms is ...
user5093249's user avatar
3 votes
Accepted

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

Scale your neural network inputs. The raw observations are in range $[0,89]$, and neural networks will cope badly with that used as inputs. The ideal case for NN for each input feature is a gaussian ...
Neil Slater's user avatar
  • 32.4k
3 votes

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

Let's first take a look at equation 6: $$ \mathbf{E} \left[ r_{t,a} \vert \mathbf{x}_{t, a} \right] = \mathbf{z}_{t, a}^{\top} \boldsymbol{\beta}^* + \mathbf{x}_{t, a}^{\top} \boldsymbol{\theta}_a^* $...
Dennis Soemers's user avatar
  • 10.3k
3 votes
Accepted

How can I incorporate domain knowledge to choose actions in the case of large action spaces in multi-armed bandits?

You will want to look into Contextual Multi-Armed Bandits. These are MAB problems that additionally involve feature vectors in some way. You'll sometimes see researchers considering problems where ...
Dennis Soemers's user avatar
  • 10.3k
3 votes
Accepted

Programming a bandit to optimize donations

It does not matter to the bandit algorithm that rewards are quantised or fractional, or that they can vary. This is true for pretty much all bandit optimisation algorithms. So just treat the $0.80 ...
Neil Slater's user avatar
  • 32.4k
3 votes

Are bandits considered an RL approach?

Let's have a look at the introduction of Chapter 2: Multi-armed Bandits in the Reinforcement Learning: An Introduction by Sutton, Barto The most important feature distinguishing reinforcement ...
Tomasz Bartkowiak's user avatar
3 votes

It is possible to solve a problem with continuous action spaces and no states with reinforcement learning?

A stateless RL problem can be reduced to a Multiarmed Bandit (MAB) problem. In such a scenario, taking an action will not change the state of the agent. So, this is the setting of a conventional MAB ...
Borhan Kazimipour's user avatar
3 votes
Accepted

How do we reach at the formula for UCB action-selection in multi-armed bandit problem?

Here is an intuitive description/explanation. $c$ is there for a trade-off between exploration and exploitation. If $c=0$ then you only consider $Q_t(a)$ (no exploration). If $c \rightarrow \infty$ ...
Brale's user avatar
  • 2,406
2 votes
Accepted

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

Although you can frame your problem as a bandit problem or RL, it has other workable interpretations. Critical information from your comments is that: Total reward is not a simple sum of all the ...
Neil Slater's user avatar
  • 32.4k
2 votes

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$?

Isn't the distribution independent of the time the arm $i$ was chosen? Each one of the two references you describe assumes the context of the random bandit problem proposed by Robbins (1952) where ...
DeepQZero's user avatar
  • 1,399
2 votes

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$?

Isn't the distribution independent of the time the arm $i$ was chosen? Yes, but you don't know which arm was chosen at time $t$, that is what $I_t$ represents. $v_i$ would represent the $i$th arms ...
David's user avatar
  • 4,910
2 votes

Why do we have two similar action selection strategies for UCB1?

In the PDF of the original paper for UCB1 you linked, in page 242-243 the authors proves why non-optimal machines get played much less (in fact, logarithmically less) than the optimal ones. $c$ ...
Namnamseo's user avatar
2 votes

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

Question: is $\bar{R}_t$ average of all rewards or average of rewards corresponding to $A_t$? It is average of all rewards seen so far. Usually a rolling recent average, so it slowly adapts to ...
Neil Slater's user avatar
  • 32.4k
2 votes
Accepted

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

If you changed this: "Multi-armed-bandit selects an action based on the future reward" To this "Multi-armed-bandit selects an action based on the expected future reward" The ...
Neil Slater's user avatar
  • 32.4k
2 votes
Accepted

Optimal sensor placement formulation as multi-armed bandit

you might have a problem with large $n$, but you can consider every possible allocation as an action, and do that as a multi-armed bandit problem. For example, say you have 2 sensors and 3 spots, ...
Alberto's user avatar
  • 2,153
2 votes
Accepted

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

Is it possible to describe wordle as a multi armed bandit problem? Yes, although the data management to present the current choice would involve constructing a state much like a reinforcement ...
Neil Slater's user avatar
  • 32.4k
1 vote
Accepted

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

You are describing an environment which requires a full Markov Decision Process (MDP) to model it and reinforcement learning (RL) algorithms to solve it. You will not be able to adapt k-armed bandit ...
Neil Slater's user avatar
  • 32.4k
1 vote

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?

The critical detail of the initial multi-k-armed bandit as it is described in the quoted text, is that the agent cannot detect or use knowledge of which bandit problem it is presented with on each ...
Neil Slater's user avatar
  • 32.4k
1 vote
Accepted

Is the Bandit Problem an MDP?

The bandit problem is an MDP. You can make the same argument about needing data to learn in the stateful MDP setting. The thing is, the data you need (the past rewards in this case) was drawn iid (...
harwiltz's user avatar
  • 1,136
1 vote

Difference in UCB performance when scaling the rewards

Epsilon greedy is unaffected by scaling of rewards, it always selects a random action with a probability of epsilon. On the other hand, if we look at the formulation of UCB (Section 2.7 of ...
James's user avatar
  • 241
1 vote

In UCB, is the actual upper bound an upper bound of an one-sided or two-sided confidence interval?

The upper bound used here is derived from Hoeffding's inequality, which provides a symmetric, two-sided confidence interval. A good pair of blog posts on how this bound used in UCB for bandits is ...
Dennis Soemers's user avatar
  • 10.3k

Only top scored, non community-wiki answers of a minimum length are eligible