基于模型的策略迭代算法

发表于 | 分类于

模型同上一篇文章 https://docle.github.io/2017/10/27/Model-based-value-iteration-algorithm/

策略迭代

确定情况下的策略迭代（Q值策略评估）

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
# -*- coding: UTF-8 -*-

import operator

xs = [0,1,2,3,4,5]
us = [-1,+1]
r = 0.5  #折扣因子
Q = []  #使用列表、列表、字典三重嵌套存储数据
hs = []  #使用列表嵌套列表存储策略迭代的 h*
vs = []  #使用列表嵌套列表存储策略迭代的 v*
tq = {}  #一个临时的字典，用来保存最新的Q计算值方便比较计算


#状态转移函数
def f(x,u):
	if x >= 1 and x <= 4:
		return x + u
	elif x == 0 or x == 5:
		return x

#奖赏函数
def reward(x,u):
	if x == 4 and u == 1:
		return 5
	elif x == 1 and u == -1:
		return 1
	else:
		return 0

#确定性情况下基于模型的Q值策略迭代
def policy_Interation():
	#初始化 h0
	hs.append(['*',1,1,1,1,'*'])
	n = 0  #对 hs 的计数
	calculate(hs[0],n)

	while True:
		n += 1
		calculate(hs[n],n)

		if operator.eq(hs[n],hs[n+1]):
			break

#策略迭代中的值计算方法
def calculate(l,t):  #接受一个路径列表和一个表示第几次计算的值作为参数
	Q.append([])
	#初始化 Qp[t][0]
	Q[t].append({})
	for x in xs:
		for u in us:
			Q[t][0][(x,u)] = 0.0
			tq[(x,u)] =  0.0
	n = 0

	while True:
		Q[t].append({})
		n += 1

		for x in xs:
			for u in us:
				y = f(x,u)
				if l[y] != '*':
					Q[t][n][(x,u)] = reward(x,u) + r * tq[(y,l[y])]
					tq[(x,u)] = Q[t][n][(x,u)]
				else:
					#当 l[y] = '*' 时，路径选择不定
					Q[t][n][(x,u)] = reward(x,u) + r * tq[(y,1)]
					tq[(x,u)] = Q[t][n][(x,u)]

		if operator.eq(Q[t][n],Q[t][n-1]):
			break

	hs.append([])
	for x in xs:
		d = Q[t][n][(x,-1)]-Q[t][n][(x,1)]
		if d < 0:
			hs[t+1].append(1)
		elif d > 0:
			hs[t+1].append(-1)
		else:
			hs[t+1].append('*')


policy_Interation()
print('h0',hs[0])
print('-------------------------------------------------------------------')
n = 0
while n+1 < len(hs):
	i = 0
	for q in Q[n]:
		print('Q' + str(i))
		print(q)
		i += 1
	print('-------------------------------------------------------------------')
	print('h' + str(n+1),hs[n+1])
	print('-------------------------------------------------------------------')
	n += 1

随机情况下的策略迭代（Q值策略评估）

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
# -*- coding: UTF-8 -*-

import operator

xs = [0,1,2,3,4,5]
us = [-1,+1]
r = 0.5  #折扣因子
Q = []  #使用列表、列表、字典三重嵌套存储数据
hs = []  #使用列表嵌套列表存储策略迭代的 h*
vs = []  #使用列表嵌套列表存储策略迭代的 v*
tq = {}  #一个临时的字典，用来保存最新的Q计算值方便比较计算

#随机情况下转移的概率函数
def p(x,u,y):  # x是开始的状态，u是采取的动作，y是最后到达的状态
	#先检查初始状态是0和5的情况
	if x == 0:
		if y == 0:
			return 1
		else:
			return 0
	elif x == 5:
		if y == 5:
			return 1
		else:
			return 0
	t = y - x
	if t == 0:
		return 0.15  #停在原地的机率是0.15
	elif t == u:
		return 0.8  #按预期方向行动的机率是0.8
	elif t == -u:
		return 0.05  #按与预期方向相反的方向行动的机率是0.05
	else:
		return 0

#随机情况的奖赏函数
def reward(x,u,y):  # x是开始的状态，u是采取的动作，y是最后到达的状态
	if x == 4 and y == 5:
		return 5
	elif x == 1 and y == 0:
		return 1
	else:
		return 0

#随机情况下基于模型的Q值策略迭代
def policy_Interation():
	#初始化 h0
	hs.append(['*',1,1,1,1,'*'])
	n = 0  #对 hs 的计数
	calculate(hs[0],n)

	while True:
		n += 1
		calculate(hs[n],n)

		if operator.eq(hs[n],hs[n+1]):
			break

#策略迭代中的值计算方法
def calculate(l,t):  #接受一个路径列表和一个表示第几次计算的值作为参数
	Q.append([])
	#初始化 Qp[t][0]
	Q[t].append({})
	for x in xs:
		for u in us:
			Q[t][0][(x,u)] = 0.0
			tq[(x,u)] =  0.0
	n = 0

	while True:
		Q[t].append({})
		n += 1

		for x in xs :
			for u in us:
				Q[t][n][(x,u)] = 0
				for y in xs:
					if l[y] == '*':
						Q[t][n][(x,u)] += p(x,u,y)*(reward(x,u,y) + r * tq[(y,1)])
					else:
						Q[t][n][(x,u)] += p(x,u,y)*(reward(x,u,y) + r * tq[(y,l[y])])
				Q[t][n][(x,u)] = round(Q[t][n][(x,u)],3)
				tq[(x,u)] = Q[t][n][(x,u)]

		if operator.eq(Q[t][n],Q[t][n-1]):
			break

	hs.append([])
	for x in xs:
		d = Q[t][n][(x,-1)]-Q[t][n][(x,1)]
		if d < 0:
			hs[t+1].append(1)
		elif d > 0:
			hs[t+1].append(-1)
		else:
			hs[t+1].append('*')

policy_Interation()
print('h0',hs[0])
print('-------------------------------------------------------------------')
n = 0
while n+1 < len(hs):
	i = 0
	for q in Q[n]:
		print('Q' + str(i))
		print(q)
		i += 1
	print('-------------------------------------------------------------------')
	print('h' + str(n+1),hs[n+1])
	print('-------------------------------------------------------------------')
	n += 1

note

  • Python 3.X对于浮点数默认的是提供17位数字的精度。
    从很大程度上说，使用浮点数时都无需考虑其行为。你只需输入要使用的数字，Python通常都会按你期望的方式处理它们:

    1
    2
    3
    4
    5
    6
    7
    >>> 0.1 + 0.1
    0.2
    >>> 0.2 + 0.2 9 0.4
    >>>2 * 0.1
    0.2
    >>>2 * 0.2
    0.4

    但需要注意的是，结果包含的小数位可能是不确定的：

    1
    2
    3
    4
    >>> 0.2 + 0.1 
    0.30000000000000004 
    >>> 3 * 0.1 
    0.30000000000000004

    所有语言都存在这种问题，没有什么可担心的。Python会尽力找到一种方式，以尽可能精确地表示结果，但鉴于计算机内部表示数字的方式，这在有些情况下很难。

    可以使用round() 函数取小数位。

  • 这次的代码实现时利用了一个临时的字典 tp，这个字典保存着 (x,u) 的最新值，因此在异步算法中计算时可以使用该字典中的值而不必分太多情况，使得计算过程更加简洁易懂。可以看出上一遍文章中的方法比这里的要复杂。