Learning by acting

Up to now, all the transitions and rewards were known. Reinforcement learning occurs when this information is not known but to be discovered by the agent interacting with the environment.

Definitions

An episode is a succession of states actions and rewards from a starting state to an end state following a policy. The utility \(u_t\) is the discounted sum of rewards of an episode from step \(t\) to the end state.

(1)\[ \begin{align}\begin{aligned}(s_0, a_1, r_1, s_1), (s_1, a_2, r_2, s_2), \cdots, (s_{M-1}, a_M, r_M, s_M)\\u_t = \sum_{i=t}^{M} r_i \gamma^{i-t}\end{aligned}\end{align} \]

Model based

The most direct way to tackle this problem is to progressively build a MDP by refining the estimations of transition and reward between encountered states. This strategy is called model-based Monte-Carlo. The “model-based” term means an MDP is explicitly built. The estimated transitions are:

(2)\[\hat{T}(s' | s, a) = \cfrac{\textrm{nb occurrences of: state $s'$ from state $s$ and action $a$}} {\textrm{nb occurrences of: state $s$ and action $a$}}\]

Similarly, the estimated rewards are:

(3)\[\hat{R}(s' | s, a) = \cfrac{\textrm{sum of rewards to $s'$ from state $s$ and action $a$}} {\textrm{nb occurrences of: state $s'$ from state $s$ and action $a$}}\]

For every occurrence of a (state, action) in an episode, all the transitions and rewards to every possible next state are updated: obviously the next state on which one lands, but also all the potential reachable other next states.

Exercise (easy)

1. For the game of the MDP course, use the model-based Monte-Carlo method to estimate the MDP transitions from the following two episodes. The policy is “always stay”.

\((s_0, a_1, r_1, s_1), (s_1, a_2, r_2, s_2), \cdots\)

(in, stay, 4, in), (in, stay, 4, in) (in, stay, 5, out)

(in, stay, 4, in) (in, stay, 5, out)

2. Did you estimate all the transitions and rewards of the MDP?

Correction

first episode:

\[ \begin{align}\begin{aligned}T(\textrm{in}|\textrm{in}, \textrm{stay}) \rightarrow \cfrac{1}{1} \rightarrow \cfrac{2}{2} \rightarrow \cfrac{2}{3}\\T(\textrm{out}|\textrm{in}, \textrm{stay}) \rightarrow \cfrac{0}{1} \rightarrow \cfrac{0}{2} \rightarrow \cfrac{1}{3}\end{aligned}\end{align} \]

second episode:

\[ \begin{align}\begin{aligned}T(\textrm{in}|\textrm{in}, \textrm{stay}) \rightarrow \cfrac{3}{4} \rightarrow \cfrac{3}{5}\\T(\textrm{out}|\textrm{in}, \textrm{stay}) \rightarrow \cfrac{1}{4} \rightarrow \cfrac{2}{5}\end{aligned}\end{align} \]

2. Since the action “quit” was not part of our policy, the transition and reward of (out|in, quit) were never estimated.

Note

From this estimated MDP, the MDP algorithms can be used and especially the value iteration to obtain the optimum policy.

Model free

If instead of estimating an MDP transitions and rewards (model-based), the qualities are directly estimated, the methods are called model-free.

Hint

Imagine you want to maintain the average of some values which arrive one by one. How would you do it?

(4)\[ \begin{align}\begin{aligned}\bar x_{0 \rightarrow N} = \cfrac{1}{N+1} \sum_{i=0}^{N} x_i = \cfrac{x_{N}}{N+1} + \cfrac{1}{N+1} \sum_{i=0}^{N-1} x_i = \cfrac{x_{N}}{N+1} + \cfrac{N}{N+1} \cfrac{1}{N} \sum_{i=0}^{N-1} x_i\\\underbrace{\bar x_{0 \rightarrow N}}_{\textrm{updated}} = \cfrac{x_{N}}{N+1} + \left( 1- \cfrac{1}{N+1}\right) \underbrace{ \bar x_{0 \rightarrow N-1}}_{\textrm{current}}\end{aligned}\end{align} \]

This is called a convex combination.

Monte-Carlo

The first method is called the model-free Monte-Carlo. Considering a whole episode following a given policy \(\pi\), every \(\hat Q_\pi(s, a)\) appearing in the episode is updated once per episode (even if they might appear several times). At the first occurrence of \((s, a)\), the remaining utility is used to update our estimate by convex combination.

(5)\[ \begin{align}\begin{aligned}(\underbrace{s, a}_{\textrm{first}}, r, s')_{t}, (s', a', r', s)_{t+1}, (\underbrace{s, a}_{\textrm{second}}, r'', s'')_{t+2} \cdots\\u_t = r_t + \gamma r_{t+1} + \gamma^2 r_{t+2} + \cdots\end{aligned}\end{align} \]

With \(N\) the number of updates seen by \(\hat Q_\pi(s, a)\):

(6)\[\begin{split}\begin{cases} Q_\pi^{(0)}(s, a) = 0 \\ \hat Q_\pi^{(N+1)}(s, a) = \left( 1- \cfrac{1}{N+1}\right) \hat Q_\pi^{(N)}(s, a) + \cfrac{1}{N+1} u_t \end{cases}\end{split}\]

Note

First, the qualities of whatever policy \(\pi\) are estimated here. There is no direct way to obtain \(\pi_{\textrm{opt}}\). Second, the full episode is required to make an update.

Exercise (easy)

For the game of the MDP course, use the model-free Monte-Carlo method on the following two episodes. The policy is “always stay” and the discount is 1.

\((s_0, a_1, r_1, s_1), (s_1, a_2, r_2, s_2), \cdots\)

(in, stay, 4, in), (in, stay, 4, in) (in, stay, 5, out)

(in, stay, 4, in) (in, stay, 5, out)

Correction

\[ \begin{align}\begin{aligned}Q^{(1)}_\pi(\textrm{in, stay}) = 0 + u_1 = 4 + 4 + 5 = 13\\Q^{(2)}_\pi(\textrm{in, stay}) = \cfrac{1}{2} Q^{(1)}_\pi(\textrm{in, stay}) + \cfrac{1}{2} u_1 = \cfrac{13}{2} + \cfrac{1}{2}(4+5) = 11\end{aligned}\end{align} \]

Sarsa

The second method is called sarsa. Instead of updating using the full utility, the local reward and the estimated next state quality are used. Contrary to the previous algorithm, the \(\hat Q_\pi(s, a)\) is updated at every occurrence of the episode. With \(N\) the number of updates seen by \(\hat Q_\pi(s, a)\):

(7)\[\hat Q_\pi^{(N+1)}(s, a) = \left( 1- \cfrac{1}{N+1}\right) \hat Q_\pi^{(N)}(s, a) + \cfrac{1}{N+1} \left( r + \gamma Q_\pi^{(N)}(s', a') \right)\]

First, note that the qualities of whatever policy \(\pi\) are estimated here. There is no direct way to obtain \(\pi_{\textrm{opt}}\). Second, note that updates are performed on the go along the episode.

Exercise (easy)

For the game of the MDP course, use the sarsa method on the following episode. The policy is “always stay” and the discount is 1. The initial \(\hat Q_\pi(\textrm{in, stay})\) is 0.

\((s_0, a_1, r_1, s_1), (s_1, a_2, r_2, s_2), \cdots\)

(in, stay, 4, in), (in, stay, 4, in) (in, stay, 5, out)

Correction

\[ \begin{align}\begin{aligned}Q^{(1)}_\pi(\textrm{in, stay}) = 0 + (r_1 + 0) = 0 + (4 + 0) = 4\\Q^{(2)}_\pi(\textrm{in, stay}) = \cfrac{1}{2} Q^{(1)}_\pi(\textrm{in, stay}) + \cfrac{1}{2} \left( r_2 + Q_\pi^{(1)}(\textrm{in, stay}) \right) = \cfrac{4}{2} + \cfrac{1}{2}(4+4) = 6\\Q^{(3)}_\pi(\textrm{in, stay}) = \cfrac{2}{3} Q^{(2)}_\pi(\textrm{in, stay}) + \cfrac{1}{3} \left( r_3 + Q_\pi^{(0)}(\textrm{out, ...}) \right) = \cfrac{12}{3} + \cfrac{1}{3}(5+0) = \cfrac{17}{3}\end{aligned}\end{align} \]

Q-learning

The third and last method is called Q-learning. Similarly to the difference between policy evaluation and value iteration for the MDPs, the Q-learning evaluates the optimum policy following whatever \(\pi\) policy.

With \(N\) the number of updates seen by \(\hat Q_{\textrm{opt}}(s, a)\):

(8)\[ \begin{align}\begin{aligned}\hat Q_{\textrm{opt}}^{(N+1)}(s, a) = \left( 1- \cfrac{1}{N+1}\right) \hat Q_{\textrm{opt}}^{(N)}(s, a) + \cfrac{1}{N+1} \left( r + \max_{a'} \gamma Q_{\textrm{opt}}^{(N)}(s', a') \right)\\\pi_\textrm{opt}(s) = \textrm{arg} \max_{a} Q_{\textrm{opt}}^{(N+1)}(s, a)\end{aligned}\end{align} \]

Exercise (easy)

For the game of the MDP course, use the Q-learning method on the three following episodes. Careful, this time the policy is “random”. The discount is still 1.

\((s_0, a_1, r_1, s_1), (s_1, a_2, r_2, s_2), \cdots\)

(in, quit, 10, out)

(in, stay, 4, in), (in, stay, 5, out)

(in, stay, 4, in), (in, quit, 10, out)

Correction

The \(N\) index has to be maintained independently of for each \(Q(s, a)\). In the previous applications, the policy was such that the “quit” action was never taken. Thus, a single counter was used. Here, due to the random policy, both “stay” and “quit” are taken, thus two indices should be maintained.

first episode

\[ \begin{align}\begin{aligned}Q^{(\textrm{updated})}_\textrm{opt}(\textrm{in, quit}) = 0 + (r_1 + 0) = 10\\\pi^{(\textrm{updated})}_\textrm{opt}(\textrm{in}) = \textrm{quit}\end{aligned}\end{align} \]

second episode

\[\begin{split}Q^{(\textrm{updated})}_\textrm{opt}(\textrm{in, stay}) &= 0 + (r_1 + \max \{0, 10\} ) = 14 \\ \pi^{(\textrm{updated})}_\textrm{opt}(\textrm{in}) &= \textrm{stay} \\ Q^{(\textrm{updated})}_\textrm{opt}(\textrm{in, stay}) &= \cfrac{1}{2} Q^{(\textrm{current})}_\textrm{opt}(\textrm{in, stay}) + \cfrac{1}{2} \left( r_2 + \max Q_\textrm{opt}^{(\textrm{current})}(\textrm{out, ...}) \right) \\ &= \cfrac{14}{2} + \cfrac{1}{2}(5+0) = \cfrac{19}{2} \\ \pi^{(\textrm{updated})}_\textrm{opt}(\textrm{in}) &= \textrm{quit}\end{split}\]

third episode

\[\begin{split}Q^{(\textrm{updated})}_\textrm{opt}(\textrm{in, stay}) &= \cfrac{2}{3} Q^{(\textrm{current})}_\textrm{opt}(\textrm{in, stay}) + \cfrac{1}{3} \left( r_1 + \max \left\{\cfrac{19}{2}, 10\right\} \right) \\ &= \cfrac{19}{3} + \cfrac{1}{3}(4+10) = 11 \\ \pi^{(\textrm{updated})}_\textrm{opt}(\textrm{in}) &= \textrm{stay} \\ Q^{(\textrm{updated})}_\textrm{opt}(\textrm{in, quit}) &= \cfrac{1}{2} Q^{(\textrm{current})}_\textrm{opt}(\textrm{in, quit}) + \cfrac{1}{2} \left( r_2 + \max Q_\textrm{opt}^{(\textrm{current})}(\textrm{out, ...}) \right) \\ &= \cfrac{10}{2} + \cfrac{1}{2}(10+0) = 10 \\ \pi^{(\textrm{updated})}_\textrm{opt}(\textrm{in}) &= \textrm{stay}\end{split}\]

Note

To summarize, RL collects information by acting in the environment:

	estimate \(\pi_{\textrm{opt}}\)	on the go	update
model based Monte-Carlo	yes	yes	just count
model free Monte-Carlo	no	no (first occurrence)	\(u_t\)
sarsa	no	yes	\(r+\gamma \hat Q_\pi(s',a')\)
Q-learning	yes	yes	\(r+ \max_{a'} \gamma \hat Q_{\textrm{opt}}(s',a')\)

For the last three, updates are performed by convex combination.

Exploration

All the previous algorithm have one major drawback: depending on the policy, some states or (state, action) will never be discovered. For the examples using the first three algorithms, the quit action has never been used, its transition or quality has never been estimated. Even considering the last algorithm (Q-learning), even though it estimates the optimum qualities / policies, it does so by following a given policy.

Following the current estimate of the optimum policy does not fix this issue. Strictly following the optimum policy will most likely ignore some less promising (state, action) which could actually be part of the overall optimum policy. One can more or less circumvent this issue using optimistic initial values of qualities. Doing so, the algorithm will automatically try at least once such tempting actions. However, this solution is not sufficient.

The most straightforward solution to help the exploration of the (state, action) space is to use a random choice of action. The most extreme version is to perform random action choices every time: random policy. However, such random action can be used to deviate from the optimum policy only a proportion \(\epsilon\) of the time. This policy is called \(\epsilon\)-greedy.