Reinforcement Learning

Sarath Chandar

•ñ¥
1-
 Programming
4. Dynamic
-

be used to
-
collection of algorithms that can compute

optimal policies given

a
perfect model
of the

environment as a Markov decision Process (MDP) .

Limitations : -
1 .
Assumes a
perfect model .

2.
Computationally expensive .

However , it
provides essential foundation for the

understanding of future algorithms

the .

Assume that the environment is a finite MDP .

i e State S action A and reward R

-

are
.

finite ,
the
dynamics
are
given by
PCs
'

.ir/s,a)-Vs-c-S,ae-Afs7,r c- R

and S
'
est ( where St
is S plus

terminal
keyidai functions
a
use
of value to
state for
and structure the episodic setting )
organize
search for good policies
.
 Optimal value fns V* ,
9.* satisfy the Bellman

optimality equations .

is = Max
a
E[R£+ ,
+✗ 4- tti )
/ St :S
,At=a]
= Max

a
E
stir
pls ',r / Sca) [+84+611]

9*15,a) = É[Rt+ -15m¥ , 9*06 ,

,a
'
) / St :S Ana]
,

= I p( slits a) ,
[r+8ma✗9*Cs!a
s !r a
'

DP
algorithms are obtained
by turning Bellman

equations into update subs for improving

approximations of the desired value functions .

ign
Policy ) :

How to compute the state value fn YT for

an
arbitrary policy I ?

(s ) = E- [ Gt 1st ] :S
 =
Er [ Rtt ,
+
rGt+ , / St :S ]

=
¥ [ Rtt ,
-18¥ ( Sta ) / f. ]
=s

4,1s) Flats ) I
-2 PCs !rls a) [rtÑv,,--s'☐
=

a
Sir
L⑨

taking
'

where 11-6151 action a' state 's

'

of
in
=
prob .

policy
under IT -

The existence and

uniqueness of YT are
guaranteed
as
long as either V21 or
eventual .
termination

is
guaranteed from all states under
policy
IT -

Note : If the env 's dynamics are

completely known ,

then ⑨ is a
system of 1st simultaneous

linear equations in 1st unknowns .

The solution is

tedious
straight forward but .

Iterative soln : -

Consider a sequence of approximate

-

value fns Voir, ,r2 each

mapping
. . .

St AIR .
 chosen ( except that
arbitrarily
The initial is
approx .

the terminal slate if any must be value )

gives
o
.
, ,

by using
Each successive is obtained
approx .

the Bellman equation for YT

update
as an

rule .

[Link] ) =
E- [ Rtt ,
+ ÑkCse→ ) / Ses]

Ealtlals )
[Link]/fr-8vkcsiDs'.rV-sc-f
= I

① vµ=YT is a fixed point for this update rule .

② the sequence He } can be shown to

converge
lo Vit as k → & under the same conditions

that guarantee the existence

of vii.

known
This
algorithm [Link]
is as
.

These updates expected

are
-
updates because
they
are based on an expectation over all
possible

next states rather than on a

sample next state .
 could two for old
arrays
one use one
NoteI : ,

Values Vkls ) and one for new values Va , Cs ) .

Or one can also do in -

place updates which

faster
converges
.

Note update of
:
of all the States
2
One round is
-

through the state

' '

called as
# space .

policy
Iterative
Note2 evaluation
only converges in

limit .

However , in practice we stop

when the
updates are
sufficiently small ,
Examples

undiscovered ,

episodic
i
setting .

[Link]/movenert:--
for the
computing
One reason value

fn for to
help find better
policy
is
policies
a
.
 for
arbitrary
Given if some
policy it
,

For some state S

,
we would like to know

not should the

charge
whether
policy
or we

to
deterministically choose an action a =/ ITG ) .

Consider
'

thereafter
'
and

selecting
a' s
'
in

following the
existing policy
it
.
The value

of this
way of behaving
is

[Link]/t --a)---zpCs:rls.a)fr+8r#siD
ohtfsia ) =
E- [ Ra -184T Cstte ) /
,

'
s
,r

If this than * G) then the

is
greater ,

'
which takes action
'
a' in state

policyfollow
new it

slates
'
s
'
and IT for rest of the would

be a
better
policy .
 Poliyimprovemertthorem (PIT )
-

Let and '

be deterministic
IT -11
an
pair of
that for S
policies such ,
all S C-

% ( silt 'Cs7 ) 741s )

Then the I be
policy good
must as as
,

better then IT
or
.

i. e. Vitals) 746 ) Ks C- f.

Ñ°¥ ( s) I 9*(5,11-161)
= E- [ Rtt ,
-184+(5++1) / St :S AET ,
'
est
]
=
Em [ Rtt -184+(4-+1) / se
,
:S
]
I ¥ , [ Reti -179+6++51116++1 )) 1St ]
:S

=ɵ[ Rtt -18 , HI ,[Retz -1841-(56-+2) /Seti ,

Att , -1T¥
] )s
=ÉLRt+ ,
-1812++2 -187+(4-+1) / st=s]
 I E# [ Rtt -184*+2+844-+3 -18%+9-+37/4:-)
,

lEÉi[ Rtt -18%72-1834-+3 -18

>
2- ,
Rent 1st - -

)
:S

=
Viti G)
-

Given the value fn .

for some
Policy
it
,

fol owing
it
greedy policy
the art
consider

the value fn .

I
'
=
argmax 9g G. a)
a

=
argmox E[ 12++1+84+01 -
+ e) / st=s ,

]
a
Atta

=
[Link]/Gr-8rn-cs' 1)
a Sir

should be
By PIT , this
greedy policy
as

good as or better than the original policy .

 The of
making policy
new
process a

that
original policy by making
an
improves on
,

it
greedy
wit '

the value fn of the

original

[Link]. s e
called
policy
is

'
T as

policy
is
the
greedy
new

then
good as
, but not better than it
,

Vq = VII.

Yi G)
,
= Max É[Rt+,trVñdst+ ) / f. ,
=s
,
]
a A- =a

Bellman
This is same as
Optimality egn .

and both it -1T

' should be
Thus He =
V* .
,

optimal policies .

Policy
n : -

Sequence of monotonically improving policies

and value fins .
 To →E ¥1T
,
Vit ,
ñzE→ . .

/ I . .
-
. .

1T¥ E→V* .

Polevaluation
icy Policy
improvement

to be
guaranteed strict

policy
Each is
a

the one (unless it is

improvement over previous

optimal )
already
.

Because a finite MDP has

only a
finite

number of policies ,
this process must
converge
and optimal value fn in
to an optimal
policy
of iterations
finite number
.

a
Val
ueIkra:- (VI )

Limitatioofyitehun : -

Each of its iteration

involves evaluation which itself is iterative

policy
an
,

evaluation
computation .
How
every ,
Policy only
converges in limit to truncate
.
When
policy
evaluation step ?

Valueikralton stops policy

evaluation after just

one
sweep .

the
update rule
for value iteration combines

the
policy improvement and truncated
policy
evaluation steps .

Ya ,
(s ) = max
a
E[Rt+ -184<(51-+1) /
, St :S , 4. =D
=
Max -2 Pls ! rlsea)[r+ Driers '☐
a
stir
tsef
For sequence fries
be
arbitrary ro the can
,

shown 4 to V* under same conditions

converge
 that
guarantee
the existence of V* .

Note :t_ : VI is obtained

by simply turning the

Bellman
optimality egn
to an
update rule .

to evaluation
Noted identical
policy except
: VI is

that it be taken over all

requires max

actions .

May
variations
of interleaving policy evaluator

improvement possible!
policy
with is

-
 Asynchronous DP : -

DP requires sweep over entire state space .

This

is not possible in problems

many
.

E- has 102° states !

Backgammon ore

Asynchronous DP → in-place DP
algorithms with

no
systematic sweeping .

Just state
update whatever is next available .

This makes it easier to intermix computation

with real time interaction To solve

given
-

.
a

MDP , iterative DP
algorithm
we can run an

at the same time that an

agent
is
actually
experiencing the MDP .

Agent 's experience →used to decide what state to

update
.

Latest value &

Policy } →
can
guide
the
agents
info from ☐p
decision
making .

-
Generalized
Policy
Iteration : GPI )
-

(
-

two
iteration consists of simultaneous
Policy ,

interacting processes

the Rhee fn
→ one
making Consistent with

(
policy Policy
the current
evaluation ?

→ the other
making the
policy greedy wart .

the current value fn ( policy improvement)

GPI idea
of
letting policy evaluation and
-

policy improvement interact

,
independent of

the
granularity and other details of two

processes .

evaluation

FE
it ✓
IT
mrgvgreedylv)
←
improvement

÷
1T¥ ✓
*
 both and
These two
processes
are
competing
cooperating .

[Link]
finds optimal time
policy
an in that is

polynomial in the number

of states and actions .

n = #
of stakes

K = #
of actions .

K ?
Total #
of deterministic policies =

direct search !
exponentially faster
is than
DP

dinner can be used to solve m☒p

programming
but scalable as DP
they not as .

are