
\slidehead{13. Reinforcement Learning \red } \bk

\centerline{[Read Chapter 13]}

\centerline{[Exercises 13.1, 13.2, 13.4]}

\bi
\item Control learning
\item Control policies that choose optimal actions
\item $Q$ learning
\item Convergence
\ei

\slidehead{Control Learning \red } \bk

Consider learning to choose actions, e.g.,

\bi
\item Robot learning to dock on battery charger
\item Learning to choose actions to optimize factory output
\item Learning to play Backgammon
\ei

Note several problem characteristics:
\bi
\item Delayed reward
\item Opportunity for active exploration
\item Possibility that state only partially observable
\item Possible need to learn multiple tasks with same sensors/effectors
\ei


\slidehead{\large One Example: TD-Gammon \red } \bk

\centerline{[Tesauro, 1995]}

\bigskip

Learn to play Backgammon

\bigskip
Immediate reward
\bi
\item +100 if win
\item -100 if lose
\item 0 for all other states
\ei

\bigskip

Trained by playing 1.5 million games against itself

\bigskip
Now approximately equal to best human player

\slidehead{\large Reinforcement Learning Problem \red } \bk

\centerline{\hbox{\psfig{file=../bookps/fig13-1.ps,width=6.0in}}}



\slidehead{Markov Decision Processes \red } \bk

Assume
\bi
\item  finite set of states $S$
\item  set of actions $A$
\item at each discrete time agent observes state $s_t \in S$ and chooses
action $a_t \in A$
\item then receives immediate reward $r_t$
\item and state changes to $s_{t+1}$
\item Markov assumption:  $s_{t+1} = \delta(s_t, a_t)$ and  $r_t = r(s_t,
a_t)$ 
\bi
\item i.e., $r_t$ and $s_{t+1}$ depend only on {\em current} state and action
\item functions $\delta$ and $r$ may be nondeterministic
\item functions $\delta$ and $r$ not necessarily known to agent
\ei
\ei



\slidehead{Agent's Learning Task \red } \bk

Execute actions in environment, observe results, and
\bi
\item learn action policy $\pi : S \ra A$ that maximizes
\[ E[r_t + \gamma r_{t+1} + \gamma^2 r_{t+2} + \ldots ] \]
from any starting state in $S$
\item here $0 \leq \gamma < 1$ is the discount factor for future rewards
\ei

\bigskip

Note something new:
\bi
\item Target function is $\pi : S \ra A$
\item but we have no training examples of form $\langle s, a \rangle$
\item training examples are of form $\langle \langle  s, a \rangle , r \rangle$
\ei

\slidehead{\large Value Function \red } \bk

To begin, consider deterministic worlds...

\bigskip

For each possible policy $\pi$ the agent might adopt, we can define an evaluation
function over states

\begin{eqnarray}
 & V^{\pi}(s) & \equiv r_{t} + \gamma r_{t+1} + \gamma^{2} r_{t+2} + ...
\nonumber \\ 
& & \equiv \sum_{i=0}^{\infty} \gamma^{i} r_{t+i} \nonumber
\end{eqnarray}

where $ r_{t}, r_{t+1}, \ldots$ are generated by following policy $\pi$
starting at state $s$

\bigskip

Restated, the task is to learn the optimal policy $\pi^{*}$
\[  \pi^{*} \equiv \argmax_{\pi} V^{\pi}(s), (\forall s) \]

\newpage
\begin{picture}(400, 500)(0,-110)
\put(130,240){\psfig{file=../bookps/rl-grid-r.ps,width=3.0in}}
\put(200,217){$r(s,a)$ (immediate reward) values}
\put(0,25){\psfig{file=../bookps/rl-grid-q.ps,width=3.0in}}
\put(80,7){$Q(s,a)$ values}
\put(250,25){\psfig{file=../bookps/rl-grid-v.ps,width=3.0in}}
\put(300,7){$V^{*}(s)$ values}
\put(130,-175){\psfig{file=../bookps/rl-grid-policy.ps,width=3.0in}}
\put(180,-193){One optimal policy}
\end{picture}
\vspace*{.25in}
%\centerline{A simple deterministic world to illustrate the basic concepts 
% of $Q$-learning.



\slidehead{What to Learn \red } \bk

We might try to have agent learn the evaluation function $V^{\pi^{*}}$ (which
we write as $V^*$)

\bigskip

It could then do a lookahead search to choose best action from any state $s$
because

\[ \pi^{*}(s) = \argmax_{a} [r(s,a) + \gamma V^{*}(\delta(s,a))] \]

A problem:
\bi
\item This works well if agent knows $\delta: S \times A \ra S$, and $r : S
\times A \ra \Re$
\item But when it doesn't, it can't choose actions this way
\ei


\slidehead{$Q$ Function \red } \bk

Define new function very similar to $V^*$

\[ Q(s,a) \equiv r(s,a) + \gamma V^{*}(\delta(s,a)) \]

If agent learns $Q$, it can choose optimal action even without knowing
$\delta$!

\[ \pi^{*}(s) = \argmax_{a} [r(s,a) + \gamma V^{*}(\delta(s,a))] \]

\[ \pi^{*}(s) = \argmax_{a} Q(s,a) \]

$Q$ is the evaluation function the agent will learn


\slidehead{Training Rule to Learn $Q$ \red } \bk

Note $Q$ and $V^*$ closely related:
\[  V^{*}(s) = \max_{a'}Q(s,a') \]

Which allows us to write $Q$ recursively as

\begin{eqnarray}
Q(s_t,a_t) &= &  r(s_t,a_t) + \gamma V^{*}(\delta(s_t,a_t))) \nonumber \\
 &= &  r(s_t,a_t) + \gamma \max_{a'}Q(s_{t+1},a') \nonumber
\end{eqnarray}

Nice!  Let $\hat{Q}$ denote learner's current approximation to $Q$.  Consider
training rule

\[ \hat{Q}(s,a) \leftarrow r + \gamma \max_{a'}\hat{Q}(s',a') \]
\noindent
where $s'$ is the state resulting from applying action $a$ in state $s$


\slidehead{$Q$ Learning for Deterministic Worlds \red } \bk

For each $s, a$ initialize table entry $\hat{Q}(s,a) \la 0$
 
\bigskip

Observe current state $s$

\bigskip

Do forever:
\bi
\item Select an action $a$ and execute it

\item Receive immediate reward $r$

\item Observe the new state $s'$

\item Update the table entry for $\hat{Q}(s,a)$ as follows:
\begin{displaymath}
\hat{Q}(s,a) \leftarrow r + \gamma \max_{a'}\hat{Q}(s',a') 
\end{displaymath}

\item $s \la s'$
\ei


\slidehead{Updating $\hat{Q}$ \red } \bk
\centerline{\hbox{\psfig{file=../bookps/rl-grid-trace.ps,width=6.5in}}}

\begin{eqnarray}
\hat{Q}(s_1,a_{right}) & \leftarrow & r + \gamma \max_{a'}\hat{Q}(s_2,a') \nonumber \\
 & \leftarrow & 0 + 0.9 \ \max \{63, 81, 100 \} \nonumber \\ & \leftarrow & 90
 \nonumber
\end{eqnarray}

\bigskip
notice if rewards non-negative, then
\[(\forall s,a,n)\ \ \hat{Q}_{n+1}(s,a) \geq \hat{Q}_{n}(s,a) \]
and 
\[(\forall s,a,n)\ \  0 \leq \hat{Q}_n(s,a) \leq Q(s,a) \]


\newpage
$\hat{Q}$ converges to $Q$.  Consider case of deterministic world where see
each $\langle s,a \rangle$ visited infinitely often.

\bigskip
{\em Proof}: Define a full interval to be an interval during which each
$\langle s, a \rangle$ is visited.  During each full interval the largest
error in $\hat{Q}$ table is reduced by factor of $\gamma$

\bigskip

 Let $\hat{Q}_{n}$ be table after $n$ updates, and $\Delta_{n}$ be the maximum
error in $\hat{Q}_{n}$; that is 
\[\Delta_{n} = \max_{s,a} |\hat{Q}_{n}(s,a) - Q(s,a)| \]

\bigskip
For any table entry $\hat{Q}_{n}(s,a)$ updated on iteration $n+1$, the error
in the revised estimate $\hat{Q}_{n+1}(s,a)$ is
\begin{eqnarray}
|\hat{Q}_{n+1}(s,a) - Q(s,a)| & = & | (r + \gamma \max_{a'}\hat{Q}_{n}(s',a')) \nonumber\\
 & & \ \  - (r + \gamma \max_{a'}Q(s',a')) | \nonumber \\
 & = & \gamma | \max_{a'}\hat{Q}_{n}(s',a') - \max_{a'}Q(s',a') | \nonumber\\
 & \leq & \gamma \max_{a'} | \hat{Q}_{n}(s',a') - Q(s',a') | \nonumber \\
 & \leq & \gamma \max_{s'',a'} | \hat{Q}_{n}(s'',a') - Q(s'',a') | \nonumber \\
|\hat{Q}_{n+1}(s,a) - Q(s,a)| & \leq & \gamma \Delta_{n} \nonumber
\end{eqnarray}

\bigskip
Note we used general fact that
\[|\max_{a}f_{1}(a) - \max_{a}f_{2}(a)| \leq \max_{a} |f_{1}(a)-f_{2}(a)|\]


\slidehead{Nondeterministic Case \red } \bk

What if reward and next state are non-deterministic?

\bigskip

We redefine $V, Q$ by taking expected values

\begin{eqnarray}
 & V^{\pi}(s) & \equiv E[ r_{t} + \gamma r_{t+1} + \gamma^{2} r_{t+2} + \ldots
 ]
\nonumber \\ 
& & \equiv E [ \sum_{i=0}^{\infty} \gamma^{i} r_{t+i} ] \nonumber
\end{eqnarray}


\[ Q(s,a) \equiv E[r(s,a) + \gamma V^{*}(\delta(s,a)) ] \]

\slidehead{Nondeterministic Case \red } \bk

$Q$ learning generalizes to nondeterministic worlds
\bigskip

Alter training rule to
\[ \hat{Q}_{n}(s,a)  \leftarrow  (1-\alpha_{n})\hat{Q}_{n-1}(s,a) + \alpha_{n}[r
+ \max_{a'}\hat{Q}_{n-1}(s',a')] \]
where
\[ \alpha_{n} = \frac{1}{1 + visits_n(s,a)} \]

\bigskip

\bigskip

Can still prove convergence of $\hat{Q}$ to $Q$ [Watkins and Dayan, 1992]


\slidehead{Temporal Difference Learning \red } \bk

$Q$ learning: reduce discrepancy between successive $Q$ estimates

\bigskip
One step time difference:
\[ Q^{(1)}(s_t,a_t) \equiv r_t + \gamma \max_{a} \hat{Q}(s_{t+1},a) \]

Why not two steps?
\[ Q^{(2)}(s_t,a_t) \equiv r_t + \gamma r_{t+1} + \gamma^2 \max_{a}
\hat{Q}(s_{t+2},a) \]

Or $n$?
\[ Q^{(n)}(s_t,a_t) \equiv r_t + \gamma r_{t+1} + \cdots
+ \gamma^{(n-1)}r_{t+n-1} + \gamma^n \max_{a}\hat{Q}(s_{t+n},a) \]

\bigskip
Blend all of these:
\[Q^{\lambda}(s_{t},a_{t})  \equiv (1- \lambda) \left[
Q^{(1)}(s_t,a_t) + \lambda Q^{(2)}(s_t,a_t) + \lambda^2 Q^{(3)}(s_t,a_t) +
\cdots \right] \]

\slidehead{Temporal Difference Learning \red } \bk
\[Q^{\lambda}(s_{t},a_{t})  \equiv (1- \lambda) \left[
Q^{(1)}(s_t,a_t) + \lambda Q^{(2)}(s_t,a_t) + \lambda^2 Q^{(3)}(s_t,a_t) +
\cdots \right] \]

Equivalent expression:
\begin{eqnarray*}
 Q^{\lambda}(s_{t},a_{t}) & = r_{t} + \gamma [ & (1 -
\lambda)
\max_{a}\hat{Q}(s_{t},a_{t}) \\
 & & + \lambda \ Q^{\lambda}(s_{t+1},a_{t+1})]
\end{eqnarray*}


TD($\lambda$) algorithm uses above training rule
\bi
\item Sometimes converges faster than $Q$ learning
\item converges for learning $V^*$ for any $0 \leq
\lambda \leq 1$ (Dayan, 1992)
\item Tesauro's TD-Gammon uses this algorithm
\ei
\slidehead{Subtleties and Ongoing Research \red } \bk

\bi
\item
Replace $\hat{Q}$ table with neural net or other generalizer
\item
Handle case where state only partially observable
\item
Design optimal exploration strategies
\item
Extend to continuous action, state
\item
Learn and use $\hat{\delta}: S \times A \ra S$
\item 
Relationship to dynamic programming
\ei
