• Up to this point, we either restored the function from the training set $(X, Y)$ (supervised learning) or searched for the structure in the set of objects $X$ (unsupervised learning)
• But how does learning work in the real world? Usually we do some action and get the result, gradually learning

• Exploration vs. Exploitation
• Credit assignment

• Multi-armed bandits — a special case of reinforcement learning with only one state, i.e., without credit assignment difficulty


• Also, there is a statistics approach (i.e. not RL): A/B testing — many users see potentially bad options; another problem is that in reality the group size should depend on the true probability values (e.g., conversions) which you don't know

Question: How to evaluate different strategies?

The quality measure of the multi-armed bandit algorithm $a$ is usually regret

$$ R(a) = \sum\limits_{t=1}^T \left(\mathbb{E}(r_{i^*_t}^t) - \mathbb{E}(r_{i^a_t}^t)\right)$$

Under synthetic conditions (when we know the probabilities), we can consider

$$ E\left( R \right) = \int\limits_{\Theta} R(a)d\Theta $$

• Initialize strategy model $\pi(a | s)$
• Repeat:
  • play $N$ sessions
  • choose the best $K$ of them and take their trajectories
  • adjust $\pi(a | s)$ so that strategy is able to maximize the probabilities of actions from the best trajectories

That there is a lot of states:

• Split the state space into sections and treat them as states
• Get probabilities from $\pi_\theta (a | s)\ - $ machine learning model: linear model, neural network, random forest (often these probabilities need to be further specified later)

• As a strategy model, we take just a neural network $\pi_\theta$
• Initialize with random weights
• At each iteration, after selecting the best trajectories, we obtain a set of pairs $$\text{Elite} = [(s_0, a_0), (s_1, a_1), (s_2, a_2), \dots, (s_H, a_H )]$$
• And perform optimization $$ \pi = \arg\max\limits_\theta \sum\limits_{s_i, a_i \in \text{Elite}} \log \pi(a_i|s_i) = \arg\max\limits_\theta \mathscr{ L}(\theta)$$
• That is $$ \theta_{t+1} = \theta_{t} + \alpha \nabla \mathscr{L}(\theta) $$

• It is unstable for small samples
• In the case of a non-deterministic environment, it chooses lucky cases (randomly played in favor of the agent)
• It is focusing on behavior in simple states
• It ignores a lot of information
• There are tasks in which the end never comes (stock market game, for instance)

Often in RL, we don't need to describe how good an action is in an absolute sense, but only how much better it is than others on average. We make this concept precise with the advantage function: $$ A_{\pi} (s, a) = Q_{\pi} (s, a) - V_{\pi} (s) $$

In practice, we have lots of problems:

• how to enumerate all possible strategies $\pi$?
• usually we don't know $r_t$ and probability distributions to calculate expectation
• also, the amount of all state is really huge and uncountable

$\quad$ The greedy strategy $\pi$ with respect to a solution of Bellman Equations $Q^*(s,a)$ (SLAE) "choose the action that maximizes $Q^*$" is optimal.

We arbitrarily initialise the function $V_{\pi}(s)$ and the strategy $\pi$. Then we repeat:

• Initialise $s$
• For each agent step:
  • Select $a$ by strategy $\pi$
  • Do action $a$, get result $r$ and next state $s^\prime$
  • Update function $V(s)$ by formula $V(s) = V(s) + \alpha \left[r + \gamma V(s^\prime) - V(s)\right]$
  • Go to the next step by assigning $s := s^\prime$

SARSA

State-Action-Reward-State-Action computes the Q-value based on the current state of the policy and is considered as an on-policy learning algorithm. Named by the quintuple (s,a,r,s',a'), the formula is as follows:

$$ Q(s,a) \leftarrow Q(s,a) + \alpha \left[r + \gamma Q(s',a') - Q(s,a)\right] $$

Q-Learning

Q-Learning is an off-policy learning algorithm that computes the Q-value based on the maximum reward that is attainable in the next state. The formula is as follows:

$$ Q(s,a) \leftarrow Q(s,a) + \alpha \left[r + \gamma \max_{a}\left[Q(s',a')\right] - Q(s,a)\right] $$

• States s: 4 consecutive frames compressed to $84 \times 84$
• Actions a: from 4 to 18, depending on the game
• Rewards r: current in-game SCORE
• Value function $Q(s, a; w)$: ConvNN with input $s$ and $|A|$ outputs

Source: V.Mnih et al. (DeepMind). Playing Atari with deep reinforcement learning. 2013

• Saves trajectories $(s_t, a_t, r_t)_{t=1}^T$ in replay memory for repeated experience replay. It is needed to prevent overfitting
• Gets approximation of the optimal value function $Q(s_t, a_t)$ for fixed current network parameters ${\color{orange} w_t}$
• Evaluates loss function for training the neural network model $Q(s, a; w)$: $$ \mathscr{L} (w) = (Q(s_t, a_t; w) - y_t)^2;\ y_t = r_t + \gamma \max_a Q(s_{t+1}, a; w) $$ with stochastic gradient SGD (by mini-batches of length 32): $$ w_{t+1} = w_{t} - \eta \left(Q(s_t, a_t; w_t) - y_t\right) \nabla_w Q(s_t, a_t; w_t) $$
• Also it is better to use two different models for max evaluation and updating (Double Q-learnig by Hado van Hasselt, 2010)

• We got acquainted with the Reinforcement Learning problem statement
• Touched a little multi-armed bandits model
• Got acquainted with the methods of cross-entropy, TD-learning and Q-learning
• Discussed Deep Q-learning Network

What else can you look at?

• Educational resource on RL produced by OpenAI
• The main book on the topic: Reinforcement Learning: An Introduction, Richard S. Sutton and Andrew G. Barto
• Yuxi Li. Resources for Deep Reinforcement Learning. 2018
• Intro to RL with David Silver, DeepMind × UCL, 2015