Reinforcement Learning

Reinforcement learning is an important type of Machine Learning where an agent learn how to behave in a environment by performing actions and seeing the results.

Inspired greatly by: An introduction to Reinforcement Learning by Thomas Simonini

The idea behind Reinforcement Learning is that an agent will learn from the environment by interacting with it and receiving rewards for performing actions.

Let’s imagine an agent learning to play Super Mario Bros as a working example. The Reinforcement Learning (RL) process can be modeled as a loop that works like this:

• Our Agent receives state S0 from the Environment (In our case we receive the first frame of our game (state) from Super Mario Bros (environment))
• Based on that state S0, agent takes an action A0 (our agent will move right)
• Environment transitions to a new state S1 (new frame)
• Environment gives some reward R1 to the agent (not dead: +1)

This RL loop outputs a sequence of state, action and reward. The goal of the agent is to maximize the expected cumulative reward.

Reward

The cumulative reward at each time step t:

Gt* = *Rt + 1 + R**t + 2 + … equivalent to $G_{t}=\sum_{k=0}^{T} R_{t+k+1}$

Rewards are discounted in time (with a factor gamma) to account for the fact that future rewards now are better than rewards in the future.

$G_{t}=\sum_{k=0}^{\infty} \gamma^{k} R_{t+k+1} \text { where } \gamma \in[0,1)$

Task types

Episodic

In this case, we have a starting point and an ending point (a terminal state). This creates an episode: a list of States, Actions, Rewards, and New States.

For instance think about Super Mario Bros, an episode begin at the launch of a new Mario and ending: when you’re killed or you’re reach the end of the level.

Continous

These are tasks that continue forever (no terminal state). In this case, the agent has to learn how to choose the best actions and simultaneously interacts with the environment.

For instance, an agent that do automated stock trading. For this task, there is no starting point and terminal state. The agent keeps running until we decide to stop him.

Learning methods

Monte Carlo (learning once / episode)

Monte Carlo When the episode ends (the agent reaches a “terminal state”), the agent looks at the total cumulative reward to see how well it did. In Monte Carlo approach, rewards are only received at the end of the game.

Then, we start a new game with the added knowledge. The agent makes better decisions with each iteration.

V(St*) ← *V*(*St) + α[Gt*−*V*(*St)]

V(St*) − *maximumexpectedfuturerewardstartingatthelaststat**e

Temporal Difference Learning (learning at each timestep)

V(St*) ← *V*(*St) + α[Rt* + 1+*γV(St* + 1)−*V*(*St)]

TD methods only wait until the next time step to update the value estimates. At time t+1 they immediately form a TD target using the observed reward Rt+1 and the current estimate V(St+1).

Exploration vs Exploitation

• Exploration is finding more information about the environment.
• Exploitation is exploiting known information to maximize the reward.

Epsilon greedy strategy

• We specify an exploration rate “epsilon,” which we set to 1 in the beginning. This is the rate of steps that we’ll do randomly. In the beginning, this rate must be at its highest value, because we don’t know anything about the values in Q-table. This means we need to do a lot of exploration, by randomly choosing our actions.
• We generate a random number. If this number > epsilon, then we will do “exploitation” (this means we use what we already know to select the best action at each step). Else, we’ll do exploration.

Three approaches to Reinforcement Learning

Value Based

In value-based RL, the goal is to optimize the value function V(s).

The value function is a function that tells us the maximum expected future reward the agent will get at each state.

The value of each state is the total amount of the reward an agent can expect to accumulate over the future, starting at that state.

The agent will use this value function to select which state to choose at each step. The agent takes the state with the biggest value.

Policy Based

In policy-based RL, we want to directly optimize the policy function π(s) without using a value function.

The policy is what defines the agent behavior at a given time.

a = π(s)

We learn a policy function. This lets us map each state to the best corresponding action.

We have two types of policy:

• Deterministic: a policy at a given state will always return the same action.
• Stochastic: output a distribution probability over actions.

Model Based

In model-based RL, we model the environment. This means we create a model of the behavior of the environment.

The problem is each environment will need a different model representation.

Value based Reinforcement Learning algorithms

Q learning

We will create a table where we’ll calculate the maximum expected future reward, for each action at each state. In terms of computation, we can transform this grid into a table. This is called a Q-table (“Q” for “quality” of the action).

Learning the Action Value Function (Q - function)

We can see this Q function as a reader that scrolls through the Q-table to find the line associated with our state, and the column associated with our action. It returns the Q value from the matching cell. This is the “expected future reward.”

Deep Q Learning

Instead of using a Q-table, we’ll implement a Neural Network that takes a state and approximates Q-values for each action based on that state.

The error (or TD error) is calculated by taking the difference between our Q_target (maximum possible value from the next state) and Q_value (our current prediction of the Q-value)

Whilst training, we can choose to retain a replay memory M, with some capacity N, from which we will train the algorithm. This helps the network’s “memory”, and prevents it from only learning about what it has immediately done.

Fixed Q targets

Using a separate network with a fixed parameter (let’s call it w-) for estimating the TD target. After T time steps w- <- w (we update the fixed parameters).

Double DQNs

When we compute the Q target, we use two networks to decouple the action selection from the target Q value generation. We:

• use our DQN network to select what is the best action to take for the next state (the action with the highest Q value).
• use our target network to calculate the target Q value of taking that action at the next state.

Dueling DQN

So we can decompose Q(s,a) as the sum of:

• V(s): the value of being at that state
• A(s,a): the advantage of taking that action at that state (how much better is to take this action versus all other possible actions at that state).

Q(s, a)=A(s, a)+V(s)

With DDQN, we want to separate the estimator of these two elements, using two new streams:

• one that estimates the state value V(s)
• one that estimates the advantage for each action A(s,a)

Prioritized experience replay 1

Prioritized Experience Replay (PER) was introduced in 2015 by Tom Schaul. The idea is that some experiences may be more important than others for our training, but might occur less frequently.

Because we sample the batch uniformly (selecting the experiences randomly) these rich experiences that occur rarely have practically no chance to be selected.

We want to take in priority experience where there is a big difference between our prediction and the TD target, since it means that we have a lot to learn about it.

But we can’t just do greedy prioritization, because it will lead to always training the same experiences (that have big priority), and thus over-fitting.

So we introduce stochastic prioritization, which generates the probability of being chosen for a replay.

But, because we use priority sampling, purely random sampling is abandoned. As a consequence, we introduce bias toward high-priority samples (more chances to be selected).

To correct this bias, we use importance sampling weights (IS) that will adjust the updating by reducing the weights of the often seen samples.

Policy based Reinforcement Learning algorithms

There are 2 types of policies:

• deterministic: given state s, π(s)=a

• stochastic: given state s, π(a

  s)=P(a**t

  s**t) (Partially Observable Markov Decision Process (POMDP))

Stochastic policies are the most common type.

Main advantages:

• convergence: because we follow the gradient to find the best parameters, we’re guaranteed to converge on a local maximum (worst case) or global maximum (best case)
• better in high dimensional action spaces: if we have a high number of continuous actions, policy based methods can model them better
• policy gradients can learn stochastic policies

Disadvantages:

• they tend to converge on a local optima
• longer training times

Objective/Policy Score function

J1(θ)=Eπ*[*G*1=*R*1+*γR2+γ2R3+…] = E**π(V(s1))

The idea is simple. If I always start in some state s1, what’s the total reward I’ll get from that start state until the end?

In a continuous environment, we can use the average value, because we can’t rely on a specific start state.

Each state value is now weighted (because some happen more than others) by the probability of the occurrence of the respected state.

$J_{avgv}(\theta)=E_{\pi}(V(s))=\sum d(s) V(s){\ where \ }d(s)=\frac{N(s)}{\sum_{s^{\prime}} N\left(s^{\prime}\right)}\ (the frequency of the state)$

Third, we can use the average reward per time step. The idea here is that we want to get the most reward per time step.

JavR*(*θ*)=*Eπ(r)=∑sd*(*s*)∑*aπθ*(*s*, *a*)*Rs**a (probability that I’m in state s) (probability that I take action a from that state under this policy) (immediate reward)

Gradient ascent

Our goal is to find the parameter θ that maximizes J(θ).

J(θ)=Eπ*[*R*(𝒯)],  *where* 𝒯 = (*si, ai*, *ri) (expected given policy) (expected future reward)

Which is the total summation of expected reward given policy.

Hybrid method

Actor Critic (A2C)

We’ll using two neural networks:

• a Critic that measures how good the action taken is (value-based)
• an Actor that controls how our agent behaves (policy-based)

The Actor Critic model is a better score function than Monte Carlo. Instead of waiting until the end of the episode as we do in Monte Carlo REINFORCE, we make an update at each step (TD Learning).

1. https://arxiv.org/abs/1511.05952