时刻的状态仅取决于t时刻的状态
而与
时刻之前的任何状态都无关时,则认为
时刻的状态
具有马尔科夫性(Markov property)
确定了,那么历史状态信息
对于确定
均不再重要,比如在围棋中下一步怎么下只跟目前的棋子的位置有关,跟他们前面怎么下成这样无关.
的状态转移概率:
>构成的元组.
代表有限状态集,
是集合中的状态转移概率矩阵,
是一个奖励函数
,
是一个属于0,1的衰减因子
时刻状态下在下一个时刻
能获得的奖励期望,也就是说我们是离开当下的状态才能得到奖励而不是进入这个状态就得到奖励.David silver指出这只是我们的一个约定,本质是一样的,读者不用纠结.
开始采样直到终止状态时所有奖励的有衰减的之和.数学表达式如下:
取0,表示某状态下的收获就是当前状态获得的奖励,不考虑后续状态,属于短视行为,当
取1,表示将考虑所有的后续状态,属于有长远眼光的行为.
变成
.这是因为
收获的期望等于它收获期望的期望.也因此,我们得到了
:
的期望就是
,因为每次离开同一个状态得到的奖励都是一个固定的值.而下一个时刻状态的期望,可以根据下一个时刻状态的概率分布得到.如果用
表示
状态下一时刻任一可能的状态:
,其中
是状态的数量.因此直接求解仅适用于对于学生马尔科夫奖励过程这类状态数比较少的小规模问题直接求解是可行的,但是当状态数量增多,就需要使用迭代法进行求解,如动态规划,蒙特卡洛评估,时序差分学习.
>构成的一个元组.
是一个有限状态集,
是一个有限行为集,
是集合中基于行为的状态转移概率矩阵
,其中
表示的是有限行为的集合
是基于状态和行为的奖励函数
,
是一个衰减因子.
表示.策略
是某一状态下基于行为集合的一个概率分布:
和一个策略
,那么状态序列
是一个符合马尔科夫过程
的采样.类似的,联合状态和奖励的序列
是一个符合马尔科夫奖励过程
的采样,并且在这个奖励过程中满足下面两个方程:
的价值函数
是在马尔科夫决策过程下基于策略
的状态价值函数,,表示从状态
开始,遵循当前策略
时所获得的收获的期望;或者说在执行当前策略时,衡量个体处在当下状态的价值大小:
的行为价值函数
表示在遵循策略
时,对当前状态
执行某一具体行为
所能达到的收获的期望:
的状态价值函数和行为价值函数后,依据贝尔曼方程,我们可以得到如下两个贝尔曼期望方程:
时,状态
的价值体现为在该状态下遵循某一策略而采取所有可能行为的价值按行为发生概率的乘积求和.
.图中状态"第三节课"在该在该策略下的价值为7.4,可以由上面的公式计算得出.(注意泡吧是一个行为不是一个状态)
表示.一旦找到这个最优策略
,那么就意味着该强化学习问题得到了解决.寻找最优策略是一件比较困难的事情,但是可以通过比较两个不同策略的优劣来确定一个较好的策略.
优于
,如果对于有限状态集里的任意一个状态
,不等式:
成立
优于或至少不差于所有其他策略.一个马尔科夫决策过程可能存在不止一个最优策略,但最优策略下的状态价值函数均等同于最优状态价值函数:
;最优策略下的行为价值函数均等同于最优行为价值函数:
:
下,对于行为集里的每一个行为a将对应一个最优行为价值
,最优策略
将给予所有最优行为价值中的最大值对应的行为以100%的概率,而其他行为被选择的概率则为0,也就是说最优策略在面对每一个状态时将总是选择能够带来最大最优行为价值的行为.这同时意味着,一旦得到
,最优策略也就找到了.因此求解强化学习问题就转变为了求解最优行为价值函数问题.
的最优价值可以由下面的贝尔曼最优方程得到:
时选择行为
的最优行为价值将不能使用最大化某一可能的后续状态的价值来计算,它由下面的贝尔曼最优方程得到:
,考虑到衰减系数
以及即时奖励为+1,因此在第三节课后采取泡吧行为的最优行为价值9.4.
有7个状态,状态转移概率如果用矩阵的形式则是一个
的矩阵,奖励函数则可以用7个标量表示,分别表示离开某一个状态得到的即时奖励值.为了方便计算,我们使用数字索引0-6来表示7个状态,用一个列表嵌套列表的方式来表示状态转移概率矩阵,同时为了方便说明和理解,我们使用两个字典来建立数字对应的状态与其实际状态名的双向映射关系.
import numpy as np
num_states = 7
i_to_n = {}#索引到状态名的字典
i_to_n["0"] = "C1"
i_to_n["1"] = "C2"
i_to_n["2"] = "C3"
i_to_n["3"] = "Pass"
i_to_n["4"] = "Pub"
i_to_n["5"] = "FB"
i_to_n["6"] = "Sleep"
n_to_i = {}#状态名到索引的字典
for i, name in zip(i_to_n.keys(), i_to_n.values()):
n_to_i[name] = int(i)
#状态转移概率矩阵
# C1 C2 C3 Pass Pub FB Sleep
Pss = [[0.0, 0.5, 0.0, 0.0, 0.0, 0.5, 0.0],
[0.0, 0.0, 0.8, 0.0, 0.0, 0.0, 0.2],
[0.0, 0.0, 0.0, 0.6, 0.4, 0.0, 0.0],
[0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0],
[0.2, 0.4, 0.4, 0.0, 0.0, 0.0, 0.0],
[0.1, 0.0, 0.0, 0.0, 0.0, 0.9, 0.0],
[0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0],
]
Pss = np.array(Pss)
#奖励函数,分别于状态对应
rewards = [-2, -2, -2, 10, 1, -1, 0]
gamma = 0.5 #折扣因子
def compute_return (start_index = 0, chain = None, gamma = 0.5) -> float:
'''
计算一个马尔科夫奖励过程中某状态的收获值
:param start_index: 要计算的状态在链中的位置
:param chain: 要计算的马尔科夫过程
:param gamma: 折扣因子
:return: 收获值
'''
retrn, power, gamma = 0.0, 0, gamma
for i in range(start_index, len(chain)):
retrn += np.power(gamma,power) * rewards[n_to_i[chain[i]]]
power += 1
return retrn
chains = [
["C1", "C2", "C3", "Pass", "Sleep"],
["C1", "FB", "FB", "C1", "C2", "Sleep"],
["C1", "C2", "C3", "Pub", "C2", "C3", "Pass", "Sleep"],
["C1", "FB", "FB", "C1", "C2", "C3", "Pub", "C1", "FB",\
"FB", "FB", "C1", "C2", "C3", "Pub", "C2", "Sleep"]
]
print(compute_return(0, chains[3], gamma=0.5))
#结果为 -3.1960449218
def compute_value(Pss, rewards, gamma = 0.05):
'''
通过求解矩阵方程的形式直接计算状态的价值
:param Pss: 状态转移概率矩阵 shape(7,7)
:param rewards: 即时奖励 list
:param gamma: 折扣因子
:return: values 各状态的价值
'''
#将rewards转为numpy数组并修改为列向量的形式
rewards = np.array(rewards).reshape((-1,1))
# np.eye(7,7)为单位矩阵,inv方法为求矩阵的逆
values = np.dot(np.linalg.inv(np.eye(7,7) - gamma * Pss), rewards)
return values
values = compute_value(Pss, rewards, gamma=0.99999)
#设置折扣因子为1的时候矩阵的逆恰好不存在 因此给一个近似于1的值
print(values)
# [[-12.54073351]
# [ 1.45690179]
# [ 4.32117045]
# [ 10. ]
# [ 0.80308417]
# [-22.53857963]
# [ 0. ]]
#根据状态和行为生成操作相关字典的键,显示字典内容
from utils import str_key, display_dict
#设置转移概率,奖励值以及读取它们的方法
from utils import set_prob, set_reward, get_prob, get_reward
#设置状态价值,策略概率以及读取它们的方法
from utils import set_value, set_pi, get_value, get_pi
#构建学生马尔科夫决策过程
S = ['浏览手机中', '第一节课', '第二节课', '第三节课', '休息中']
A = ['浏览手机', '学习', '离开浏览', '泡吧', '退出学习']
R = {}#奖励Rsa字典
P = {}#状态转移概率Pss'a字典
gamma = 1.0 #折扣因子
#根据学生马尔科夫决策过程示例的数据设置状态转移概率和奖励, 默认概率为1
set_prob(P, S[0], A[0], S[0]) #浏览手机中-浏览手机->浏览手机中
set_prob(P, S[0], A[2], S[1]) #浏览手机中-离开浏览->第一节课
set_prob(P, S[1], A[0], S[0]) #过于重复的内容就不列举了 大家自己明白就好
set_prob(P, S[1], A[1], S[2])
set_prob(P, S[2], A[1], S[3])
set_prob(P, S[2], A[4], S[4])
set_prob(P, S[3], A[1], S[4])
set_prob(P, S[3], A[3], S[1], p = 0.2)
set_prob(P, S[3], A[3], S[2], p = 0.4)
set_prob(P, S[3], A[3], S[3], p = 0.4)
set_reward(R, S[0], A[0], -1) #浏览手机中-浏览手机->-1
set_reward(R, S[0], A[2], 0)
set_reward(R, S[1], A[0], -1)
set_reward(R, S[1], A[1], -2)
set_reward(R, S[2], A[1], -2)
set_reward(R, S[2], A[4], 0)
set_reward(R, S[3], A[1], 10)
set_reward(R, S[3], A[3], 1)
MDP = (S, A, R, P, gamma)
print("----状态转移概率字典(矩阵)信息:----")
display_dict(P)
print("----奖励字典(函数)信息:----")
display_dict(R)
# ----状态转移概率字典(矩阵)信息:----
# 浏览手机中_浏览手机_浏览手机中: 1.00
# 浏览手机中_离开浏览_第一节课: 1.00
# 第一节课_浏览手机_浏览手机中: 1.00
# 第一节课_学习_第二节课: 1.00
# 第二节课_学习_第三节课: 1.00
# 第二节课_退出学习_休息中: 1.00
# 第三节课_学习_休息中: 1.00
# 第三节课_泡吧_第一节课: 0.20
# 第三节课_泡吧_第二节课: 0.40
# 第三节课_泡吧_第三节课: 0.40
#
# ----奖励字典(函数)信息:----
# 浏览手机中_浏览手机: -1.00
# 浏览手机中_离开浏览: 0.00
# 第一节课_浏览手机: -1.00
# 第一节课_学习: -2.00
# 第二节课_学习: -2.00
# 第二节课_退出学习: 0.00
# 第三节课_学习: 10.00
# 第三节课_泡吧: 1.00
.代码如下:
#设置行为策略:pi(a|.) = 0.5
Pi = {}
set_pi(Pi, S[0], A[0], 0.5)#浏览手机中-浏览手机
set_pi(Pi, S[0], A[2], 0.5)#其他重复的就不多列举
set_pi(Pi, S[1], A[0], 0.5)
set_pi(Pi, S[1], A[1], 0.5)
set_pi(Pi, S[2], A[1], 0.5)
set_pi(Pi, S[2], A[4], 0.5)
set_pi(Pi, S[3], A[1], 0.5)
set_pi(Pi, S[3], A[3], 0.5)
print("----策略转移概率字典(矩阵)信息:----")
display_dict(Pi)
#初始时价值为空, 访问时会返回0
print("----价值字典(函数)信息:----")
V = {}
display_dict(V)
# ----策略转移概率字典(矩阵)信息:----
# 浏览手机中_浏览手机: 0.50
# 浏览手机中_离开浏览: 0.50
# 第一节课_浏览手机: 0.50
# 第一节课_学习: 0.50
# 第二节课_学习: 0.50
# 第二节课_退出学习: 0.50
# 第三节课_学习: 0.50
# 第三节课_泡吧: 0.50
#
# ----价值字典(函数)信息:----
时某行为
的价值
,依据公式如下.该计算过程不涉及策略.
def compute_q(MDP, V, s, a):
'''
根据给定的MDP,价值函数V,计算状态行为对s,a的价值q_sa
:param MDP: 马尔科夫决策函数
:param V: 价值函数V
:param s: 状态
:param a: 行为
:return: 在s状态下a行为的价值q_sa
'''
S, A, R, P, gamma = MDP
q_sa = 0
for s_prime in S:
q_sa += get_prob(P, s, a, s_prime) * get_value(V, s_prime)
q_sa = get_reward(R, s, a) + gamma * q_sa
return q_sa
def compute_v(MDP, V, Pi, s):
'''
给定MDP下依据某一策略Pi和当前状态价值函数V计算某状态s的价值
:param MDP: 马尔科夫决策过程
:param V: 状态价值函数V
:param Pi: 策略
:param s: 某状态s
:return: 某状态的价值v_s
'''
S, A, R, P, gamma = MDP
v_s = 0
for a in A:
v_s += get_pi(Pi, s, a) * compute_q(MDP, V, s, a)#一个状态的价值可以由该状态下所有行为价值表达
return v_s
#根据当前策略使用回溯法来更新状态价值,本章不做要求
def update_V(MDP, V, Pi):
'''
给定一个MDP和一个策略,更新该策略下的价值函数
'''
S, _, _, _,_ = MDP
V_prime = V.copy()
for s in S:
V_prime[str_key(s)] = compute_v(MDP, V_prime, Pi, s)
return V_prime
#策略评估,得到该策略下最终的状态价值
def policy_evaluate(MDP, V, Pi, n):
'''
使用n次迭代计算来评估一个MDP在给定策略Pi下的状态价值,初始时为V
'''
for i in range(n):
V = update_V(MDP, V, Pi)
return V
V = policy_evaluate(MDP, V, Pi, 100)
display_dict(V)
# ----价值字典(函数)信息:----
# 浏览手机中: -2.31
# 第一节课: -1.31
# 第二节课: 2.69
# 第三节课: 7.38
# 休息中: 0.00
v = compute_v(MDP, V, Pi, "第三节课")
print("第三节课在当前策略下的最终价值为{:.2f}".format(v))
#第三节课在当前策略下的最终价值为7.38
def compute_v_from_max_q(MDP, V, s):
'''
根据一个状态下的所有可能的行为价值中最大一个来确定当前状态价值
'''
S, A, R, P, gamma = MDP
v_s = -float('inf')
for a in A:
qsa = compute_q(MDP, V, s, a)
if qsa >= v_s:
v_s = qsa
return v_s
def update_V_without_pi(MDP, V):
'''
在不以来策略的情况下直接通过后续状态的价值来更新状态价值
'''
S, _, _, _, _ = MDP
V_prime = V.copy()
for s in S:
V_prime[str_key(s)] = compute_v_from_max_q(MDP, V_prime, s)
return V_prime
def value_iterate(MDP, V, n):
'''
价值迭代
'''
for i in range(n):
V = update_V_without_pi(MDP, V)
return V
V = {}
#通过价值迭代得到最优状态价值
print("----最优状态价值信息----")
V_star = value_iterate(MDP, V, 4)
display_dict(V_star)
# ----最优状态价值信息----
# 浏览手机中: 6.00
# 第一节课: 6.00
# 第二节课: 8.00
# 第三节课: 10.00
# 休息中: 0.00
#验证最优行为价值
s,a = "第三节课", "泡吧"
q = compute_q(MDP, V_star, s, a)
print("在状态{}选择行为{}的最优价值为:{:.2f}".format(s,a,q))
#在状态第三节课选择行为泡吧的最优价值为:9.40
def str_key(*args):
'''
将参数用"_"连接起来作为字典的键,需注意参数本身可能会是tuple或者list型,
比如类似((a,b,c),d)的形式
'''
new_arg = []
for arg in args:
if type(arg) in [tuple, list]:
new_arg += [str(i) for i in arg]
else:
new_arg.append(str(arg))
return "_".join(new_arg)
def set_dict(target_dict, value, *args):
target_dict[str_key(*args)] = value
def set_prob(P, s, a, s1, p=1.0):#设置概率字典
set_dict(P, p, s, a, s1)
def get_prob(P, s, a, s1):#获取概率值
return P.get(str_key(s, a, s1), 0)
def set_reward(R, s, a, r): #设置奖励值
set_dict(R, r, s, a)
def get_reward(R, s, a):#获取奖励值
return R.get(str_key(s,a), 0)
def display_dict(target_dict):#显示字典内容
for key in target_dict.keys():
print("{}: {:.2f}".format(key, target_dict[key]))
print("")
def set_value(V, s, v):#设置价值字典
set_dict(V, v, s)
def get_value(V, s):#获取价值字典
return V.get(str_key(s), 0)
def set_pi(Pi, s, a, p = 0.5):#设置策略字典
set_dict(Pi, p, s, a)
def get_pi(Pi, s, a):#获取策略(概率)值
return Pi.get(str_key(s,a),0)