- RL David Silver
- Lecture Introduction
- Lecture 2 : MDP
- Lecture 3: Planning by Dynamic Programming
- Lecture 4: Model-Free Prediction
- Lecture 5: Model-Free Control
- Example of Greedy Action Selection
- Monte-Carlo Control
- GLIE Monte-Carlo Control
- Convergence of Sarsa
- Sarsa on the Windy Gridworld
- Backward View Sarsa(λ)
- Sarsa(λ) Gridworld Example
- Off-Policy Learning
- Importance Sampling
- Importance Sampling for Off-Policy Monte-Carlo
- Importance Sampling for Off-Policy TD
- Q-Learning
http://www0.cs.ucl.ac.uk/staff/d.silver/web/Teaching.html
-
Solving the Bellman Equation
- computation directly by inverse martix
- iterative calculation
- Dynamic programming
- Monte-Carlo evaluation
- Temporal-Difference learning
- DP
- Policy Evaluation
- iterative application of Bellman expectation backup
- Policy Iteration
- Evaluate the policy π
- Improve the policy by acting greedily
- Value Iteration
- iterative application of Bellman optimality backup
- Policy Evaluation
-
MC
- Prediction
- idea: value = mean return
- methods
- First-Visit Monte-Carlo Policy Evaluation
- Every-Visit Monte-Carlo Policy Evaluation
- Incremental Monte-Carlo Updates
- tricks: Incremental Mean
- Control
- Policy evaluation
- Policy improvement
- ε-Greedy Policy Improvement
- GLIE: Greedy in the Limit with Infinite Exploration (GLIE)
- eg: ε = 1/k
- Prediction
-
TD
- Prediction
- TODO
- Control
- Natural idea: use TD instead of MC in our control loop
- Policy evaluation: Sarsa
- Policy improvement
- ε-greedy policy improvement
- Prediction
-
Off-Policy Learning : Q-Learning
-
Relationship Between DP and TD
-
vπ(s)
- = expectation of all qπ(s,a)
- π(s) maybe a stochastic policy
- in state s , there maybe 4 available actions: E,W,N,S, and the policy maybe 30% E, 70% S , so π(a=W|s) = π(a=N|s) = 0 ???
-
qπ(s,a)
- = immediate reward r(s,a) + γ·expectation of all vπ(s')
-
vπ(s) / qπ(s,a) can represent recursively.
-
v*(s)
- = max vπ(s) over all policy
- = max q*(s,a) over all action
- = max of immediate reward r(s,a) over all action
-
- γ·expectation of all v*(s')
-
-
q*(s,a)
- = max qπ(s,a) over all policy
- = immediate reward r(s,a) + γ·expectation of all v*(s')
- There is no supervisor, only a reward signal
- Feedback is delayed, not instantaneous
- Time really matters (sequential, non i.i.d data)
- iid : independent and identically distributed
- Agent’s actions affect the subsequent data it receives
- A reward Rt is a scalar feedback signal
- Indicates how well agent is doing at step t
- The agent’s job is to maximise cumulative reward
- Reinforcement learning is based on the reward hypothesis
- Definition (Reward Hypothesis)
- All goals can be described by the maximisation of expected cumulative reward
- Goal: select actions to maximise total future reward
- Actions may have long term consequences
- Reward may be delayed
- It may be better to sacrifice immediate reward to gain more long-term reward
- Agent 有两个输入： observation and reward. 这些输入共同决定 下一步措施。
- At each step t the agent:
- Receives observation Ot
- Receives scalar reward Rt
- Executes action At
- The environment:
- Receives action At
- Emits observation Ot+1
- Emits scalar reward Rt+1
- The history is the sequence of observations, actions, rewards
- Ht = O₁,R₁,A₁,...,At-1,Ot,Rt
- Histroy is huge. It is normally not useful.
- What happens next depends on the history:
- The agent selects actions
- The environment selects observations/rewards
- State is the information used to determine what happens next
- Formally, state is a function of the history: st = f(Ht)
- The environment state Sᵉt is the environment’s private representation
- The environment state is not usually visible to the agent
- Even if Sᵉt is visible, it may contain irrelevant information
- something about multi-agents
- for each agent, it can consider all other agents and their interacting with environment to be a part of environment.
- The agent state sªt is the agent’s internal representation
- It can be any function of history:
- sªt = f(Ht)
- an information state , a.k.a Markov state , contains all useful information from the history.
- Definition A state St is Markov if and only if
- P[St+1 |St ] = P[St+1 |S₁,...,St ]
- "The future is independent of the past given the present"
- H1:t -> St -> Ht+1:∞
- Once the state is known, the history may be thrown away
- i.e. The state is a sufficient statistic of the future
- The environment state Sᵉt is Markov
- The history Ht is Markov
- Full observability: agent directly observes environment state
- Ot = Sªt = Sᵉt
- Agent state = environment state = information state
- Formally, this is a Markov decision process (MDP)
- Partial observability: agent indirectly observes environment:
- A robot with camera vision isn’t told its absolute location
- A trading agent only observes current prices
- A poker playing agent only observes public cards
- Now agent state != environment state
- Formally this is a partially observable Markov decision process (POMDP)
- Agent must construct its own state representation Sªt , how to do that ? We have many ways :
- Complete history: Sªt = Ht
- Beliefs of environment state:
- Recurrent neural network
- Policy: agent’s behaviour function
- Value function: how good is each state and/or action
- Model: agent’s representation of the environment
- A policy is the agent’s behaviour
- It is a map from state to action, e.g.
- Deterministic policy: a = π(s)
- Stochastic policy: π(a|s) = P(At=a | st=s)
- Value function is a prediction of future reward
- Used to evaluate the goodness/badness of states
- And therefore to select between actions, e.g.
- vπ(s) = Eπ [Rt+1 + γRt+2 + γ²Rt+3 + ... |St=s ]
- A model predicts what the environment will do next
- Transitions: T predicts the next state
- Rewards: R predicts the next (immediate) reward, e.g.
- T = P[ St+1=s' | St=s, At=a ]
- Model is not necessary.
- Policy
- Arrows represent policy π(s) for each state s
- Value Function
- Numbers represent value vπ(s) of each state s
- Model
- Agent may have an internal model of the environment
- Dynamics: how actions change the state
- Rewards: how much reward from each state
- The model may be imperfect
- Grid layout represents transition model
- Numbers represent immediate reward R from each state s (same for all a)
- Value Based
No Policy (Implicit)(can get the optimal action by do 1-step expectimax search)- Value Function
- Policy Based
- Policy
No Value Function
- Actor Critic
- Policy
- Value Function
- Model Free
- Policy and/or Value Function
No Model
- Model Base
- Policy and/or Value Function
- Model
Two fundamental problems in sequential decision making
- Reinforcement Learning:
- The environment is initially unknown
- The agent interacts with the environment
- The agent improves its policy
- Planning:
- A model of the environment is known
- The agent performs computations with its model (without any external interaction)
- The agent improves its policy
- a.k.a. deliberation, reasoning, introspection, pondering, thought, search
- Reinforcement learning is like trial-and-error learning
- The agent should discover a good policy
- From its experiences of the environment
- Without losing too much reward along the way
- Exploration finds more information about the environment
- Exploitation exploits known information to maximise reward
- It is usually important to explore as well as exploit
- Prediction: evaluate the future
- Given a policy
- calculate vπ
- Control: optimise the future
- Find the best policy
- calculate v*
- MDP formally describe an environment for reinforcement learning
- Where the environment is fully observable
- i.e. The current state completely characterises the process
- state 特征化了 我们所需要知道的一切
- Almost all RL problems can be formalised as MDPs, e.g
- Optimal control primarily deals with continuous MDPs
- Partially observable problems can be converted into MDPs
- Bandits are MDPs with one state
- "The future is independent of the past given the present"
- H1:t -> St -> Ht+1:∞
- Definition A state St is Markov if and only if
- P[St+1 |St ] = P[St+1 |S₁,...,St ]
- The state captures all relevant information from the history
- Once the state is known, the history may be thrown away
- i.e. The state is a sufficient statistic of the future
- For a Markov state s and successor state s′, the state transition probability is defined by
- Pss' = P[St+1=s'|St=s]
- State transition matrix P defines transition probabilities from all states s to all successor states s′,
- where each row of the matrix sums to 1.
- A Markov process is a memoryless random process,
- Definition: A Markov Process (or Markov Chain) is a tuple ( S,P )
- S is a (finite) set of states
- P is a state transition probability matrix
- Pss' = P[St+1=s'|St=s]
- A Markov Reward Process is a tuple ( S ,P , R , γ )
- R is a reward function , Rs = 𝔼( Rt+1 | St=s )
- γ is a discount factor, γ ∈ [0, 1]
-
the return Gt t is the total discounted reward from time-step t
- Gt = Rt+1 + γRt+2 + ...
- = ∑k=∞₀ γᵏRt+k+1
- why here is no expectation ?
- because here G is just one sample from our MRP , later we will talk about expectation.
- The value of receiving reward R afte k + 1 time-steps is γᵏR.
- This values immediate reward above delayed reward.
- γ close to 0 leads to ”myopic” evaluation
- γ close to 1 leads to ”far-sighted” evaluation
- Gt = Rt+1 + γRt+2 + ...
-
Most Markov reward and decision processes are discounted
-
It is sometimes possible to use undiscounted Markov reward processes
- if all sequences terminate
Most Markov reward and decision processes are discounted. Why?
- Mathematically convenient to discount rewards
- Avoids infinite returns in cyclic Markov processes
- Uncertainty about the future may not be fully represented
- If the reward is financial, immediate rewards may earn more interest than delayed rewards
- Animal/human behaviour shows preference for immediate reward
- It is sometimes possible to use undiscounted Markov reward processes (i.e. γ = 1),
- e.g. if all sequences terminate.
- The value function v(s) gives the long-term value of state s
- Definition: The state value function v(s) of an MRP is the expected return starting from state s
- v(s)=𝔼[Gt |St =s]
value is expectation because the environment is stochastic.
The value function can be decomposed into two parts:
- immediate reward Rt+1
- discounted value of successor state γ·v(St+1)
- v(s)=𝔼[ Rt+1 + γ·v(St+1) |St =s]
- v(s) = Rs + γ·∑s'∈S Pss'·v(s')
- The Bellman equation can be expressed concisely using matrices,
- v = R + γPv
- where v is a column vector with one entry per state
Bellman Equation for MRPs has no concept of maximum. So t can be expressed concisely using matrices. And here the bellman exuation is a linear equation , as a result it can be solved directly. It is not true when we meet MDP.
- The Bellman equation is a linear equation
- Computational complexity is O(n³) for n states
- Direct solution only possible for small MRPs
- There are many iterative methods for large MRPs, e.g.
- Dynamic programming
- Monte-Carlo evaluation
- Temporal-Difference learning
-
A Markov decision process (MDP) is a Markov reward process with decisions.
-
It is an environment in which all states are Markov
-
( S , A, P , R , γ )
-
Given an MDP M= ( S , A, P , R , γ ) , and a policy π
- The state sequence S1, S2, ... is a Markov process (S,Pπ)
- The state and reward sequence S1,R2,S2, ... is is a Markov reward process ( S,Pπ, Rπ, γ )
- Definition: A policy π is a distribution over actions given states,
- π(a|s) = ℙ[At =a | St =s ]
- A policy fully defines the behaviour of an agent
- MDP policies depend on the current state (not the history)
- Given an MDP M = <S,A,P,R,γ> and a policy π
- The state sequence S1, S2, ... is a Markov process < S, Pπ >
- The state and reward sequence S1, R2, S2, ... is a Markov reward process < S, Pπ, Rπ, γ >
you can get different rewards. It is not one expectation any more , there are different expectations depending how we act
- The state-value function can again be decomposed into immediate reward plus discounted value of successor state,
- The action-value function can similarly be decomposed
With a fixed policy π, MDP Bellman Expectation Equation can also be expressed concisely using matrices.
v* is the maximum value function over all policies.
v* is the maximum, q* is the average (expectation).
- Value Iteration
- Policy Iteration
- Q-learning
- Sarsa
given an MDP -> Policy evaluation -> Policy Improvement: improve the policy by acting greedily with respect to vπ
Qestion: how to apply greedy algorithm on vπ
A: 1-step expertimax for each state.
π'(s) = argmaxa∈A qπ(s,a)
- Policy evaluation 一般迭代数次，就可以得到 optimal vπ，更多的迭代并不能带来任何提升
- Does policy evaluation need to converge to vπ ?
- Or should we introduce a stopping condition
- eg. ε-convergence of value function
- 观察 bellman 方程 更新value函数的大小，假如value 函数更新的很小的话，这就表明你可以停下来了。即使这样，你还是很容易做无用功。
- Or simply stop after k iterations of iterative policy evaluation?
- For example, in the small gridworld k = 3 was sufficient to achieve optimal policy
- Why not update policy every iteration? i.e. stop after k = 1
- This is equivalent to value iteration (next section)
Policy Iteration: follow fixed policy
Value Iteration: choose optimal action every step.
The ordering is very important. 这就产生了 priorities sweeping.
- This lecture:
- Model-free prediction
- Estimate the value function of an unknown MDP
它可能不是最有效率的方法，但是它是最有效果，也是最广泛使用在实践中的方法。
- MC methods learn directly from episodes of experience
- MC is model-free: no knowledge of MDP transitions / rewards
- MC learns from complete episodes: no bootstrapping
- MC uses the simplest possible idea: value = mean return
- Caveat: can only apply MC to episodic MDPs
- All episodes must terminate
- Monte-Carlo policy evaluation uses empirical mean return instead of expected return
我们还有收集尽量多的样本，从某个特定个点开始发生的状态中收集。 问题是我们要怎样做到这一步，在我们不能反复将状态重设回那个点的情况下 ？
We have 2 different ways to do this.
- To evaluate state s
- The first time-step t that state s is visited in an episode,
- Increment counter N(s) ← N(s) + 1
- Increment total return S(s) ← S(s) + Gt
- not whole episode , only from state s to termination
- Value is estimated by mean return V(s) = S(s)/N(s)
- By law of large numbers, V(s) → vπ(s) as N(s) → ∞
- To evaluate state s
- Every time-step t that state s is visited in an episode,
- Increment counter N(s) ← N(s) + 1
- Increment total return S(s) ← S(s) + Gt
- Value is estimated by mean return V(s) = S(s)/N(s)
- Again, V(s) → vπ(s) as N(s) → ∞
- 求平均值也可以 递增计算, 但是需要记录 counter
- V(St) ← V(St) + 1/N(St)·(Gt - V(St))
- In non-stationary problems, it can be useful to track a running mean, i.e. forget old episodes.
- V(St) ← V(St) + α( Gt - V(St) )
- TD methods learn directly from episodes of experience
- TD is model-free: no knowledge of MDP transitions / rewards
- TD learns from incomplete episodes, by bootstrapping
- TD updates a guess towards a guess
你正在开车，对面突然开过来一辆卡车，你感觉马上要撞车了，庆幸的是最后两车错开了。
- MC
- 并不会记录到这次濒死的体验
- TD
- 你能预感到危险，你会降速，立刻更新你的 value值，而不用等到你死了。
- MC
- 你最终到家了，看到实际花了43分钟，然后才能更新你的每一个估计值
- TD
- you update immediately every step
- TD exploits Markov property
- Usually more efficient in Markov environments
- MC does not exploit Markov property
- Usually more effective in non-Markov environments
- eg. In a POMDP, TD(0) won't work very well. MC will still do the right thing.
we also did one step lookahead, but we didn't sample. We have to know the dynamics.
- Bootstrapping: update involves an estimate
- MC does not bootstrap
- DP bootstraps
- TD bootstraps
- Sampling: update samples an expectation
- MC samples
- DP does not sample
- TD samples
You open the right door forever if you improve policy greedily. The problem is you actually really don't know what is value of left door if you only tried once.
现在我们想让整个过程更加有效。
首先，我们在动态规划过程中已经看到过，it is not necessary to go all the way to the top of the line "Q=qπ". It is not necessary to fully evaluate your policy. Sometimes you could just take a few steps to evaluate your policy. And you've got enough information to guide you to a better policy without wasting many many interations to collect more information.
那么在 蒙特卡洛环境之中又是怎么样的呢？我们可以设想一个极端的情况：say why not do this every single episode?
So we are gonna run 1 episode -- make the robot do 1 episode , collect all the steps along that episode, update the q value just for those steps ,so basically 1 new return. so for every state-action we take along that return , we're gonna update that mean value just of those visted states tried actions along that episode.
So 1 episode , 1 seqence of updates for that return. And then we improved our policy straightway.
So the idea is always to act greedily with repest to the freshest , most recent estimative value function. If I run 1 episode, you can really update you value function something slightly better. And why you continue using the old value ?
How to balance exploration and exploitation ?
这是我们第一个完整的解决方案.
In practice , we don't worry about the step-size αt. Sometimes we even don't worry about GLIE. And Sarsa typically works anyway.
The graph basically shows the learning curve of running Sarsa.
We run 170 episodes in total. This graph shows the accumulative total finishing time-steps for each episodes. ( time-step 全局累加 )
So the first episode takes about 2000 steps to complete. 因为它一开始的时候，对于该怎么走一无所知，所以一开始就是随机地走来走去。
当他一次实验成功后，在运行下一组实验的时候，就变得快了不少。 The slope of curve is increaing.
- eligibility traces
- eligibility traces is for all state-action pair.
- So we got a new table. each cell corresponds to a state-action pair.
- eligibility traces 可以告诉你，你采取的每一个 state-action 能够得到多少奖赏 后 被 罚多少分。
- 当你跑完整组实验之后，你得到了一跟萝卜。那么究竟哪个state-action pair 才能让我得到胡萝卜呢？你的eligibility traces 会给你作出最优评估，告诉你怎样才能得到胡萝卜。 可能是离胡萝卜最近的 state-action， 也可能是 出现最频繁的 state-action。
- 某个time-step , 所有 没有被执行到 E(s,a)会衰减
- 每走一步 对所有 state-action 进行一次更新
- 但只有跑完一个完整实验之后，才会出现最终的奖励。这就意味着你只有最终达到了目标 才能收集到信息。
- 因此这些箭头可以告诉你，当整个实验跑完的时候，你所得到的有效更新是什么样的。
Everything so far 所有的讨论都是建立在已知策略的基础之上的。同时 我所用的策略就是我在学习的策略。
但是依然有很多情况，我们想考虑是 怎么评估一些其他的策略。
So MC is really a bad idea for off-policy.
TD is still not so good for off-policy even if it is much much better than MC.
This is specific to TD(0).