无痛的增强学习入门：价值迭代

| 作者 冯超 7 他的粉丝 发布于 2017年8月31日. 估计阅读时间: 19 分钟 | GMTC大前端的下一站，PWA、Web框架、Node等最新最热的大前端话题邀你一起共同探讨。

4 价值迭代

4.1 N轮策略迭代

from contextlib import contextmanager
import time

@contextmanager
def timer(name):
start = time.time()
yield
end = time.time()
print '{} COST:{}'.format(name, end - start)

def policy_iteration(self):
iteration = 0
while True:
iteration += 1
with timer('Timer PolicyEval'):
self.policy_evaluation()
with timer('Timer PolicyImprove'):
ret = self.policy_improvement()
if not ret:
break

def policy_iteration_demo():
np.random.seed(0)
env = Snake(10, [3,6])
agent = TableAgent(env.state_transition_table(), env.reward_table())
agent.policy_iteration()
print 'return_pi={}'.format(eval(env,agent))
print agent.policy

policy evaluation proceed 94 iters.
Timer PolicyEval COST:0.139311790466
Timer PolicyImprove COST:0.00118112564087
policy evaluation proceed 62 iters.
Timer PolicyEval COST:0.0768580436707
Timer PolicyImprove COST:0.000974178314209
policy evaluation proceed 46 iters.
Timer PolicyEval COST:0.0550677776337
Timer PolicyImprove COST:0.00197505950928
Iter 3 rounds converge
return_pi=84
[0 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0
0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0]

policy evaluation proceed 46 iters.
Timer PolicyEval COST:0.0480210781097
Timer PolicyImprove COST:0.00193190574646
Iter 3 rounds converge
return_pi=84
[0 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0
0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0]

policy evaluation proceed 11 iters.
Timer PolicyEval COST:0.011638879776
Timer PolicyImprove COST:0.00103783607483
Iter 4 rounds converge
return_pi=84
[0 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0
0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0]

policy evaluation proceed 2 iters.
Timer PolicyEval COST:0.00178599357605
Timer PolicyImprove COST:0.00106501579285
Iter 7 rounds converge
return_pi=84
[0 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0
0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0]

4.2 从动态规划的角度谈价值迭代

”某个位置走两步的最大奖励“＝max([这一步的奖励 + 从到达位置出发走一步最大奖励 for 走法 in 可能的走法])

4.3 价值迭代的实现

def value_iteration(self):
iteration = 0
while True:
iteration += 1
new_value_pi = np.zeros_like(self.value_pi)
for i in range(1, self.state_num): # for each state
value_sas = []
for j in range(0, self.act_num): # for each act
value_sa = np.dot(self.table[j, i, :], self.reward + self.gamma * self.value_pi)
value_sas.append(value_sa)
new_value_pi[i] = max(value_sas)
diff = np.sqrt(np.sum(np.power(self.value_pi - new_value_pi, 2)))
if diff < 1e-6:
break
else:
self.value_pi = new_value_pi
print 'Iter {} rounds converge'.format(iteration)
for i in range(1, self.state_num):
for j in range(0, self.act_num):
self.value_q[i,j] = np.dot(self.table[j,i,:], self.reward + self.gamma * self.value_pi)
max_act = np.argmax(self.value_q[i,:])
self.policy[i] = max_act

Iter 3 rounds converge
Timer PolicyIter COST:0.190360069275
return_pi=84
[0 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0
0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0]
Iter 94 rounds converge
Timer ValueIter COST:0.0884821414948
return_pi=84
[0 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0
0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0]