9 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 ...
  • 1,972
5 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 ...
  • 36.3k
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 ...
  • 25.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 ...
  • 1,112
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 ...
  • 36.3k
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 ...
  • 25.4k
4 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&...
  • 1,112
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-...
  • 9,649
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 ...
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 ...
  • 25.4k
3 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. ...
  • 25.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^* $...
  • 9,649
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 ...
  • 9,649
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 ...
  • 25.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 ...
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 ...
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$ ...
  • 2,286
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 ...
  • 25.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 ...
  • 1,112
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 ...
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$ ...
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 ...
  • 25.4k
1 vote
Accepted

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

in the limit as the number of steps increases Means for the value we are interested in (number of samples for action $a$, let's call that $N(a)$), then we want to find $$\lim\limits_{t \to \infty} N(...
  • 25.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 ...
  • 25.4k
1 vote

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 (...
  • 1,061
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 ...
  • 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 ...
  • 9,649
1 vote

Multi Armed Bandits with large number of arms

Without any knowledge on the references you came across, I am assuming that the authors were considering common applications of MAB (planning, online learning, etc.) for which the time horizon is ...
  • 196
1 vote

When discounted MAB is useful?

One of the reasons a discount factor is used, is to make sure the reward maximization is a well-defined problem and to make the sum of all rewards convergent. In the MAB problem, the number of trials ...

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