Quick Notes on Reinforcement Learning

Introduction

In this series of blog posts, I intend to write my notes as I go through Richard S. Suttonโ€™s excellent Reinforcement Learning: An Introduction (1).

I will try to formalise the maths behind it a little bit, mainly because I would like to use it as a useful personal reference to the main concepts in RL. I will probably add a few remarks about a possible implementation as I go on.

Relationship between agent and environment

Context and assumptions

The goal of reinforcement learning is to select the best actions availables to an agent as it goes through a series of states in an environment. In this post, we will only consider discrete time steps.

The most important hypothesis we make is the Markov property:

At each time step, the next state of the agent depends only on the current state and the current action taken. It cannot depend on the history of the states visited by the agent.

This property is essential to make our problems tractable, and often holds true in practice (to a reasonable approximation).

With this assumption, we can define the relationship between agent and environment as a Markov Decision Process (MDP).

Definition 1. A Markov Decision Process is a tuple (๐’ฎ,๐’œ,โ„›,p)(\mathcal{S}, \mathcal{A}, \mathcal{R}, p) where:

  • ๐’ฎ\mathcal{S} is a set of states,
  • ๐’œ\mathcal{A} is an application mapping each state sโˆˆ๐’ฎs \in \mathcal{S} to a set ๐’œ(s)\mathcal{A}(s) of possible actions for this state. In this post, we will often simplify by using ๐’œ\mathcal{A} as a set, assuming that all actions are possible for each state,
  • โ„›โŠ‚โ„\mathcal{R} \subset \mathbb{R} is a set of rewards,
  • and pp is a function representing the dynamics of the MDP: p:๐’ฎร—โ„›ร—๐’ฎร—๐’œโ†ฆ[0,1]p(sโ€ฒ,r|s,a):=โ„™(St=sโ€ฒ,Rt=r|Stโˆ’1=s,Atโˆ’1=a),\begin{align} p &: \mathcal{S} \times \mathcal{R} \times \mathcal{S} \times \mathcal{A} \mapsto [0,1] \\ p(s', r \;|\; s, a) &:= \mathbb{P}(S_t=s', R_t=r \;|\; S_{t-1}=s, A_{t-1}=a), \end{align} such that โˆ€sโˆˆ๐’ฎ,โˆ€aโˆˆ๐’œ,โˆ‘sโ€ฒ,rp(sโ€ฒ,r|s,a)=1. \forall s \in \mathcal{S}, \forall a \in \mathcal{A},\quad \sum_{s', r} p(s', r \;|\; s, a) = 1.

The function pp represents the probability of transitioning to the state sโ€ฒs' and getting a reward rr when the agent is at state ss and chooses action aa.

We will also use occasionally the state-transition probabilities: p:๐’ฎร—๐’ฎร—๐’œโ†ฆ[0,1]p(sโ€ฒ|s,a):=โ„™(St=sโ€ฒ|Stโˆ’1=s,Atโˆ’1=a)=โˆ‘rp(sโ€ฒ,r|s,a).\begin{align} p &: \mathcal{S} \times \mathcal{S} \times \mathcal{A} \mapsto [0,1] \\ p(s' \;|\; s, a) &:= \mathbb{P}(S_t=s' \;|\; S_{t-1}=s, A_{t-1}=a) \\ &= \sum_r p(s', r \;|\; s, a). \end{align}

Rewarding the agent

Definition 2. The expected reward of a state-action pair is the function r:๐’ฎร—๐’œโ†ฆโ„r(s,a):=๐”ผ[Rt|Stโˆ’1=s,Atโˆ’1=a]=โˆ‘rrโˆ‘sโ€ฒp(sโ€ฒ,r|s,a).\begin{align} r &: \mathcal{S} \times \mathcal{A} \mapsto \mathbb{R} \\ r(s,a) &:= \mathbb{E}[R_t \;|\; S_{t-1}=s, A_{t-1}=a] \\ &= \sum_r r \sum_{s'} p(s', r \;|\; s, a). \end{align}

Definition 3. The discounted return is the sum of all future rewards, with a multiplicative factor to give more weights to more immediate rewards: Gt:=โˆ‘k=t+1Tฮณkโˆ’tโˆ’1Rk, G_t := \sum_{k=t+1}^T \gamma^{k-t-1} R_k, where TT can be infinite or ฮณ\gamma can be 1, but not both.

Deciding what to do: policies

Defining our policy and its value

A policy is a way for the agent to choose the next action to perform.

Definition 4. A policy is a function ฯ€\pi defined as ฯ€:๐’œร—๐’ฎโ†ฆ[0,1]ฯ€(a|s):=โ„™(At=a|St=s).\begin{align} \pi &: \mathcal{A} \times \mathcal{S} \mapsto [0,1] \\ \pi(a \;|\; s) &:= \mathbb{P}(A_t=a \;|\; S_t=s). \end{align}

In order to compare policies, we need to associate values to them.

Definition 5. The state-value function of a policy ฯ€\pi is vฯ€:๐’ฎโ†ฆโ„vฯ€(s):=expected return when starting in s and following ฯ€vฯ€(s):=๐”ผฯ€[Gt|St=s]vฯ€(s)=๐”ผฯ€[โˆ‘k=0โˆžฮณkRt+k+1|St=s]\begin{align} v_{\pi} &: \mathcal{S} \mapsto \mathbb{R} \\ v_{\pi}(s) &:= \text{expected return when starting in $s$ and following $\pi$} \\ v_{\pi}(s) &:= \mathbb{E}_{\pi}\left[ G_t \;|\; S_t=s\right] \\ v_{\pi}(s) &= \mathbb{E}_{\pi}\left[ \sum_{k=0}^{\infty} \gamma^k R_{t+k+1} \;|\; S_t=s\right] \end{align}

We can also compute the value starting from a state ss by also taking into account the action taken aa.

Definition 6. The action-value function of a policy ฯ€\pi is qฯ€:๐’ฎร—๐’œโ†ฆโ„qฯ€(s,a):=expected return when starting from s, taking action a, and following ฯ€qฯ€(s,a):=๐”ผฯ€[Gt|St=s,At=a]qฯ€(s,a)=๐”ผฯ€[โˆ‘k=0โˆžฮณkRt+k+1|St=s,At=a]\begin{align} q_{\pi} &: \mathcal{S} \times \mathcal{A} \mapsto \mathbb{R} \\ q_{\pi}(s,a) &:= \text{expected return when starting from $s$, taking action $a$, and following $\pi$} \\ q_{\pi}(s,a) &:= \mathbb{E}_{\pi}\left[ G_t \;|\; S_t=s, A_t=a \right] \\ q_{\pi}(s,a) &= \mathbb{E}_{\pi}\left[ \sum_{k=0}^{\infty} \gamma^k R_{t+k+1} \;|\; S_t=s, A_t=a\right] \end{align}

The quest for the optimal policy

References

  1. R. S. Sutton and A. G. Barto, Reinforcement learning: an introduction, Second edition. Cambridge, MA: The MIT Press, 2018.