【强化学习纲要】2 马尔科夫决策过程
- 2.1 MDP
- 2.1.1 马尔科夫链(Markov Chain)
- 2.1.2 马尔科夫奖励过程(MRP)
- 2.1.3 马尔科夫决策过程(MDP)
- 2.2 MDP中的价值函数
- 2.2.1 Bellman expectation equation
- 2.2.3 Backup Diagram for V π V^\pi Vπ
- 2.2.4 Policy evaluation
- 2.2.5 举例
- 2.3 MDP的控制
- 2.3.1 policy iteration
- 2.3.2 value iteration
周博磊《强化学习纲要》
学习笔记
课程资料参见:https://github.com/zhoubolei/introRL.
教材:Sutton and Barton
《Reinforcement Learning: An Introduction》
2.1 MDP
Agent对环境的交互
马尔可夫决策过程(MDP)是强化学习的一个基本框架。在马尔可夫决策过程是fully observable,部分观测的问题同样可以转化成MDP问题。
我们说一个状态满足于马尔科夫,意思是一个状态的下一个状态取决于当前状态,而跟当前状态之前的状态都没关系
S t S_t St转成 S t + 1 S_{t+1} St+1等于之前所有的状态,未来的转移对过去是独立的,只取决于现在。
2.1.1 马尔科夫链(Markov Chain)
描述状态转移可以用状态转移矩阵
表示agent在
s
t
s_t
st这个状态下的时候到下一个状态的概率
2.1.2 马尔科夫奖励过程(MRP)
- MRP = Markov Chain + reward
- 与马尔科夫链相比,多了一个奖励函数
到达某个状态后,可以获得的奖励 - 折扣函数
- Horizon的定义
同一个episode可以看作一个游戏环节或者整个轨迹的长度,是由有限个步数决定的 - Return的定义
把奖励进行折扣获得收益
越往后定义的奖励折扣越多,说明我们更希望得到现有的奖励,未来的都会打折扣。 - 状态价值函数
V
t
(
s
)
V_t(s)
Vt(s)
在MRP中定义为return的期望
意味着从这个状态有可能获得多大的价值,也可以看作是对未来可能获得收益的当前价值的表现 - 为什么需要Discount Factor γ \gamma γ
- 避免无穷的奖励
- 把不确定性表述出来
- 让奖励变得有价值,尽可能快的得到奖励而不是后面得到
- 从人的行为分析可知想要尽可能快的得到奖励
- γ = 0 \gamma=0 γ=0:只关注当前奖励
- γ = 1 \gamma=1 γ=1:未来获得的奖励和当前获得的奖励是一样的
举例:
解法1:
蒙特卡洛采样的方法:从
s
4
s_4
s4采样很多轨迹,并把return都计算出来,取平均得到
s
4
s_4
s4的价值
解法2:
MRP价值函数满足贝尔曼等式(Bellman equation)
贝尔曼等式定义了当前状态和未来状态之间的相关,
V
(
s
′
)
V(s')
V(s′)表示未来的所有状态
P
(
s
′
∣
s
)
P(s'|s)
P(s′∣s)表示当前状态转移到未来状态的概率。
第二部分可以看作一个Discounted sum of future reward,加上当前可以立刻得到的奖励,组成Bellman equation
-
Bellman equation推导过程
-
Bellman equation描述了状态间迭代的关系(iterative relations)
-
MRP中Bellman equation的矩阵形式
通过矩阵求逆的方法,可以求得 V V V
-
Analytic solution:
矩阵求逆的过程是 O ( N 3 ) O(N^3) O(N3)的复杂度,所以当状态很多的时候,比如有100万个状态,P就是个100万*100万的矩阵,求逆非常的复杂。
因此通过Analytic solution去求解V只能对于很小的MRPs -
迭代的方法求解价值函数(用于解状态很多的情况)
- 动态规划的方法(Dynamic Programming)
- 蒙特卡洛的方法(Monte-Carlo evaluation)
- 动态规划和蒙特卡洛的结合(Temporal-Difference learning)
-
Monto Carlo 算法求解价值函数
类似于采样的方法,在得到一个MRP后,从某一个状态开始,把小船放进去让他随波逐流,这样就会产生一个轨迹(episode);于是就会得到一个奖励,然后积累起来;在积累了一定数量过后,除以轨迹,得到价值。
举例:
- 动态规划的方法
通过一直迭代Belleman equation,当更新的状态和最后差距不大的时候
(收敛),更新停止,输出最新的V’(s)作为当前的价值
2.1.3 马尔科夫决策过程(MDP)
-
相对于MRP,MDP多了action(decision)
-
状态转移也多了一个条件:
采取某一种行为,未来的状态会不同,不仅依赖于当前的状态,也依赖于当前状态采取的行为,会决定未来的价值走向。 -
价值函数也多了个条件
-
Policy in MDP
- Policy定义了在某一个状态的时候应该采取怎样的行为
- 当我们知道当前状态后,带入策略函数得到probability,象征着在某一个状态的时候采取怎样的行为,它可能是概率,也可能是决定性的
- 假设Policies是静态的,不同的时间点都是在对这个policy function进行采样
-
当我们已知一个MDP和policy π \pi π的时候,可以把MDP转换成MRP
已知在MDP中P是基于当前state和当前action,因为已知policy function,即在每一个状态可能采取的行为的概率,就可以直接把action进行加和,就会等于MRP的状态转移,没有包括action。
同理
- MP/MRP和MDP的差异
对于MDP,首先要决定采取某种行为,到达黑色的节点;到达黑色节点后,有多大的概率到达某一个状态,当前状态和未来状态转移过程中多了一层决策行为。
2.2 MDP中的价值函数
- 与MRP类似,但是期望是基于policy
π
\pi
π,policy决定过后,通过对policy进行采样,计算得到价值函数
- 这里我们另外引入了一个q函数(action-value function)
某一个状态,某一个行为,可能得到的return的期望 - 价值函数和q函数之间的关系
把价值函数的action直接加和它的policy得到价值函数
2.2.1 Bellman expectation equation
Bellman expectation equation描述了当前状态对未来状态的关联
通过对价值函数的定义,进行分解,这里的期望是对于policy
对于q函数也可以做对应得分解
把上面两式分别交叉代入:
象征着当前状态的q函数与未来状态的q函数的关联
象征着当前状态价值与未来状态价值的关联
2.2.3 Backup Diagram for V π V^\pi Vπ
对于某一个状态,上一个状态是和未来价值线性相关的。
这里包含两层加和,第一层加和推到黑色节点后再往上走一层推到根节点,即当前状态。
Backup Diagram定义了未来一个状态与上一个状态的关联。
同样对于q函数也可以有类似的推导
根节点是q函数的节点,是黑色节点,下一时刻q函数是叶子节点(四个),通过加和将q节点到达白色节点s后,再进行加和推回到当前q函数。
未来q函数到当前q函数的关联性。
2.2.4 Policy evaluation
- 已知MDP和policy π \pi π,计算价值函数,用来评估策略会得到多大的奖励。
- 也叫prediction,预测当前采取的策略未来会产生多大的价值。
2.2.5 举例
MDP不同的是,有一个主体agent去控制,使得能够更好的获取奖励。
- Policy evaluation
把Bellman equation拿出来进行迭代就可算出
2.3 MDP的控制
MDP的核心问题
- Prediction
给定一个MDP和policy π \pi π,计算每个state的价值函数 - Control
寻找一个最佳的策略
输入:MDP
输出:最佳价值函数(optimal value function) v* 和最佳策略(optimal policy) π ∗ \pi^* π∗ - 在MDP里面,prediction和control都可以通过动态规划解决。
动态规划(Dynamic Programming)
我们可以把一个问题分解,分解成最佳子结构(optimal substructure),当把子结构求得后,总共组成一个最优的解。
- MDP是满足动态规划的要求的。
- Bellman equation里面我们把它分解成一个递归的结构。如果子状态得到一个值,未来状态和子状态是直接相连的,那么可以推算出来。
- 价值函数储存最佳的解。
Policy evaluation on MDP
当我们给定MDP后,我们有一个事先定好的Policy,我们可以获得多少的价值呢?
解决:将Bellman equation backup反复迭代,直到收敛
方法:Synchronous backup
当得到上一时刻v(t)的时候,通过递归的关系能够推出下一时刻的值
由于已经知道policy function,可以简化成MRP的形式:
通过迭代这个更为简化的函数,也可以得到每个状态的价值。
举例1:Small Gridworld
已知状态和状态转移,可以进行一个简短的迭代,就可以算出每一个状态的价值。
举例2:
https://cs.stanford.edu/people/karpathy/reinforcejs/gridworld_dp.html
每个状态都是固定的随机策略。
连续点击Policy Evaluation,直到收敛
Optimal Value Function
- 搜索一种
π
\pi
π,会得到每个状态的值最大的情况:
- 此时的策略叫做最佳策略:
- 如果得到一个optimal value function后,我们就称为MDP被解了。
- 最佳的价值函数是一致的(optimal value function),但是可能有多个optimal polices可以取得相同的最佳价值。
寻找optimal policy
当取得最佳价值函数后,可以通过采取某个行为对q函数进行极大化,得到最佳价值。
策略搜索方法
- 方法一:穷举
假设状态个数有限,行为个数(可能性)有限,则policy有 ∣ A ∣ ∣ S ∣ |A|^{|S|} ∣A∣∣S∣个,算出每一种的value function得到最优。但是这样效率非常低
因此我们通常采取下面两种解策略搜索的方法:
- 方法二:policy iteration
- 方法三:value iteration
MDP Control
寻找最佳策略的过程就是MDP Control的过程,得到一个最大的价值函数。
- 对于一个事先定好的MDP过程,当agent采取策略的时候,策略一般都是
- deterministic
- Stationary(不会随着时间的变换)
- 不一定是唯一的,多种行为都会去到相同的价值。
2.3.1 policy iteration
主要由两个步骤组成:
步骤1:policy evaluation。优化policy
π
\pi
π后,得到一个最新的policy,先保持这个policy不变,先估计它的价值v。(当前的policy
π
\pi
π估计v)
得到v函数后可以进一步推算出q函数,然后取q函数的极大化,
步骤2:改进策略,通过在q函数上做贪心搜索(greedy),进一步改进策略。
这两步迭代进行。
有初始化的V和
π
\pi
π,上面曲线是当前V的值,下面是policy的值。
逐渐迭代然后收敛。
那么步骤2是如何改进策略的呢?
- 当得到v值后,可以通过reward function和状态转移算出q函数
- 每一个状态会得到新一轮的policy
可以把q函数看作q table,横轴是状态,纵轴是可能的action。q函数得到后即可得到q table,对于每一个状态。
每一个状态采取能够使得q最大化的action
单调递增的Policy
思想:通过采取greedy(argmax)的操作,是会得到更好或者不变的policy,而不会使它价值函数变差
推导过程:
- 当改进停止后,我们会得到一个最佳的策略;取它极大化的action后,就会变成它的价值函数:
- 因此有了Bellman optimality equation。当Bellman optimality equation满足时,MDP已经达到最佳状态。
q函数取最大的action的值就等于它的value function。只有在收敛后,达到最佳policy时才满足。
Bellman optimality equation
很重要,之后的q learning也是基于Bellman optimality equation进行的。
只有当整个状态达到最佳状态的时候才满足。
2.3.2 value iteration
也是基于Bellman optimality equation推导得到。
思想:为了得到最佳的v*(s),把Bellman optimality equation当成update rule来进行,把它当作一个迭代的等式,不停迭代,最后逐渐趋向于最佳策略。
动态展现:
Demo
https://cs.stanford.edu/people/karpathy/reinforcejs/gridworld_dp.html
-
Policy iteration
第一步:点击Policy Evaluation
第二步:点击Policy Update
第三步:反复点击Policy Evaluation 直至没有变化
第四步:点击Policy Update
第五步:重复第三步和第四步,直至没有变化
-
value iteration
点击Toggle Value iteration
Policy iteration and value iteration on FrozenLake
https://github.com/cuhkrlcourse/RLexample/tree/master/MDP
- policy iteration代码
import numpy as np
import gym
from gym import wrappers
from gym.envs.registration import register
def run_episode(env, policy, gamma = 1.0, render = False):
""" Runs an episode and return the total reward """
obs = env.reset()
total_reward = 0
step_idx = 0
while True:
if render:
env.render()
obs, reward, done , _ = env.step(int(policy[obs]))
total_reward += (gamma ** step_idx * reward)
step_idx += 1
if done:
break
return total_reward
def evaluate_policy(env, policy, gamma = 1.0, n = 100):
scores = [run_episode(env, policy, gamma, False) for _ in range(n)]
return np.mean(scores)
#更新policy
def extract_policy(v, gamma = 1.0):
""" Extract the policy given a value-function """
policy = np.zeros(env.env.nS)
for s in range(env.env.nS):
q_sa = np.zeros(env.env.nA)
for a in range(env.env.nA):
q_sa[a] = sum([p * (r + gamma * v[s_]) for p, s_, r, _ in env.env.P[s][a]])
#得到q函数后,极大化得到新的policy
policy[s] = np.argmax(q_sa)
return policy
def compute_policy_v(env, policy, gamma=1.0):
""" Iteratively evaluate the value-function under policy.
Alternatively, we could formulate a set of linear equations in iterms of v[s]
and solve them to find the value function.
"""
v = np.zeros(env.env.nS)
eps = 1e-10
while True:
prev_v = np.copy(v)
#迭代Bellman expactation equation
for s in range(env.env.nS):
policy_a = policy[s]
#不停的更新v[s]
v[s] = sum([p * (r + gamma * prev_v[s_]) for p, s_, r, _ in env.env.P[s][policy_a]])
#当满足收敛条件时
if (np.sum((np.fabs(prev_v - v))) <= eps):
# value converged
break
return v
def policy_iteration(env, gamma = 1.0):
""" Policy-Iteration algorithm """
policy = np.random.choice(env.env.nA, size=(env.env.nS)) # initialize a random policy
max_iterations = 200000
gamma = 1.0
for i in range(max_iterations):
#根据policy得到compute_policy_v,返回当前状态的价值函数
old_policy_v = compute_policy_v(env, policy, gamma)
#更新policy,policy improvement
new_policy = extract_policy(old_policy_v, gamma)
if (np.all(policy == new_policy)):
print ('Policy-Iteration converged at step %d.' %(i+1))
break
policy = new_policy
return policy
if __name__ == '__main__':
env_name = 'FrozenLake-v0' # 'FrozenLake8x8-v0'
env = gym.make(env_name)
optimal_policy = policy_iteration(env, gamma = 1.0)
scores = evaluate_policy(env, optimal_policy, gamma = 1.0)
print('Average scores = ', np.mean(scores))
- value iteration代码
import numpy as np
import gym
from gym import wrappers
from gym.envs.registration import register
def run_episode(env, policy, gamma = 1.0, render = False):
""" Evaluates policy by using it to run an episode and finding its
total reward.
args:
env: gym environment.
policy: the policy to be used.
gamma: discount factor.
render: boolean to turn rendering on/off.
returns:
total reward: real value of the total reward recieved by agent under policy.
"""
obs = env.reset()
total_reward = 0
step_idx = 0
while True:
if render:
env.render()
obs, reward, done , _ = env.step(int(policy[obs]))
total_reward += (gamma ** step_idx * reward)
step_idx += 1
if done:
break
return total_reward
def evaluate_policy(env, policy, gamma = 1.0, n = 100):
""" Evaluates a policy by running it n times.
returns:
average total reward
"""
scores = [
run_episode(env, policy, gamma = gamma, render = False)
for _ in range(n)]
return np.mean(scores)
def extract_policy(v, gamma = 1.0):
""" Extract the policy given a value-function """
policy = np.zeros(env.env.nS)
for s in range(env.env.nS):
q_sa = np.zeros(env.action_space.n)
for a in range(env.action_space.n):
for next_sr in env.env.P[s][a]:
# next_sr is a tuple of (probability, next state, reward, done)
p, s_, r, _ = next_sr
q_sa[a] += (p * (r + gamma * v[s_]))
policy[s] = np.argmax(q_sa)
return policy
def value_iteration(env, gamma = 1.0):
""" Value-iteration algorithm """
v = np.zeros(env.env.nS) # initialize value-function
max_iterations = 100000
eps = 1e-20
for i in range(max_iterations):
prev_v = np.copy(v)
#核心迭代过程
#整个过程没有policy的参与,并没有临时变量来存储policy,只是在迭代过程中尽可能快的得到价值函数optimal value function
for s in range(env.env.nS):
#算出q函数
q_sa = [sum([p*(r + gamma * prev_v[s_]) for p, s_, r, _ in env.env.P[s][a]]) for a in range(env.env.nA)]
#取得max
v[s] = max(q_sa)
if (np.sum(np.fabs(prev_v - v)) <= eps):
print ('Value-iteration converged at iteration# %d.' %(i+1))
break
return v
if __name__ == '__main__':
env_name = 'FrozenLake-v0' # 'FrozenLake8x8-v0'
env = gym.make(env_name)
gamma = 1.0
#当收敛过后,返回optimal_v的值
optimal_v = value_iteration(env, gamma);
#extract policy,最后返回最佳的policy
policy = extract_policy(optimal_v, gamma)
policy_score = evaluate_policy(env, policy, gamma, n=1000)
print('Policy average score = ', policy_score)
Policy iteration和Value iteration的对比
- 都是为了解MDP的控制问题
- Policy iteration由两部分组成:policy evaluation + policy improvement
- Value iteration:直接寻找optimal value function + one policy extraction。当我们把optimal value function得到后,执行一次最佳策略提取过程得到最佳策略。
总结
课程作业
https://github.com/cuhkrlcourse/ierg6130-assignment