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


3

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 distribution with mean 0, standard deviation 1. You don't need that to be perfect, though. A simple scale - divide each element by $30$ and subtract $1.5$ - will ...


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


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


2

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

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


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