7

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 problems. These algorithms have their strengths and weaknesses depending on the details of the underlying problem. Multi-Armed Bandit is not even an algorithm - it ...


4

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 think the key thing here is the caveat but not all. What you have is a fully-featured MDP (states, actions, rewards, timesteps where next reward and next state ...


3

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 problem: at each time step, the agent selects an action to either perform an exploration or exploitation move. It then records the reward of the taken action ...


3

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 therefore is to compare your choices with the ideal choices. This makes sense in MABs, because although the primary goal is to gain the most reward, the learning part ...


3

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 the details. However, compared to $\epsilon$-greedy (widely used in RL), UCB1 is more computationally expensive, given that, for each action, you need to ...


3

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 because the state does not change over time. Two notable consequences are that (i) pulling a lever does not change the internals of any slot machine (e.g. the ...


3

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 you get to see a single feature vector per timestep (like an "environment state" you're in) which may provide useful information. You'll also sometimes see ...


3

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 donation as a real valued reward of 0.8, that occurs on a single timestep. Treating a single reward on a single timestep as if it were multiple rewards across ...


3

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$ then you only consider exploration term. $\frac{\ln t}{N_t(a)}$ is there to balance out exploration term. If you consider a simple case where you only have one ...


2

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 learning from other types of learning is that it uses training information that evaluates the actions taken rather than instructs by giving correct actions. This is ...


2

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 problems as a special case of the general RL problem. The first chapter of this part of the book describes solution methods for the special case of the ...


2

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 results from 66 different machines. There are interactions between machines. Total reward is deterministic. This looks like a problem in combinatorial optimisation....


2

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 the underlying reward distributions of each bandit are fixed. Therefore, yes, the underlying distributions are independent of the current time. Is it because the ...


2

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 distribution, whereas you want the distribution of the arm that was chosen at time $t$, which is $v_{I_t}$. $X_{I_t,t}$ is used to represent the arm you chose at ...


2

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 usually measured in terms of regret. This is the difference between (i) the amount of rewards accumulated by an oracle policy having prior knowledge about the true ...


2

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-armed bandit problems usually only have just one "state", and then this requirement turns into only requiring the ability to enumerate actions. In RL ...


1

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 (conditioned on the arm) and is not actually a trajectory. For instance, once you learn an optimal policy, you no longer need to gather data and the sequence of ...


1

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" with probability $\epsilon$ means selecting an action randomly with probability $\epsilon$ at each timestep and selecting an action greedily with ...


1

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 Reinforcement Learning, Sutton and Barto): $$A_t \doteq \underset{a}{\operatorname{argmax}} [\mathcal{Q}_t(a) + c \sqrt{\frac{\ln t}{N_t(a)}}]$$ Where $Q_t(a)= \frac{R_1 +...


1

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 derived can be found here: First steps: Explore-then-Commit The Upper Confidence Bound Algorithm Indeed, in practice when using this UCB for bandits, we do not ...


1

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$ decides whether they indeed would, and $c=\sqrt{2}$ is the minimum choice of $c$. We want to show that the number of runs for non-optimal machines ($n_i$, for non-...


1

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. Essentially MDPs are a strict generalisation of contextual bandits. You can model a CB as an MDP but not vice-versa. In some very specific cases you can convert MDP ...


1

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 is typically finite owing to some sort of budget in the number of trials. Hence, this is less of problem. However, by all means discounts are still valid and ...


1

The weighted average stands for a linear combination of all values, such that the sum of all weights is 1. More specifically, if you denote the rewards by a vector $X$, the weighted average will be taking the dot product between $X$ and a vector $W$ such that $0 \le W_i \le 1$ and the sum of all $W_i$ is 1. If each $W_i = 1/n$ it will be a weighted average ...


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