提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档
文章目录
前言内核一、MC Basic二、例子说明三、MC Basic代码1.伪代码2.代码3.代码结果
总结
前言
个人笔记，恳求纠错，请勿转载
内核
本次要学习的是Monte Carlo算法，这是我们学的第一个model-free的算法，它和policy iteration本质上的区别就是没有模型。 在机器学习中，没有模型就意味着必须有足够多的数据来支撑研究，因此MC算法的数学核心就是大数定律。
一、MC Basic
在policy iteration 基于模型的部分是什么呢，根据李航老师的《统计学习方法》可以知道，policy iteration 中的模型其实就是条件概率。（理解为做实验如果你提前知道实验成功的概率，就是心中有数这个实验有多少概率会成功，其实这就是一个模型。如果你只是得到return而没有提前知道实验概率那就是无模型) policy iteration 中的其中一步： 求解最大的qΠk的时候，其中的两个条件概率就是模型。所以为了避免模型，我们选择第二种求解方法，直接求解期望： 实际上就是多执行该动作几次，将得到的诸多return求平均。 所以MC Basic本质上与policy iteration 是一样的：
只是在setp1时policy iteration可以根据模型直接算出qΠk，而MC Basic则需要取多个episodes，然后取平均值，其它一模一样捏。
二、例子说明
先说明一下这个例子，这个例子各个s1中的policy都是确定的，如图箭头所示。 那我们第一步就是进行估计qΠk，由于对全部九个格子进行策略更新需要时间成本太多，只考虑s1： 从上图可知qΠ0（s1，a2）= qΠ0(s1, a3)为最大qΠk，所以选a2和a3都可以，这样我们就完成了对s1这个state策略的更新，个人感觉很简单。 episode的长度选择距离终点最远空格到达终点所要步数的值的大小就行。 如上面例子所示s1到达终点需要五步，所以episode选5比较好。
三、MC Basic代码
1.伪代码
1.遍历每个s对应的a，收集足够多的episodes，分别求出qΠk； 2.选取最大的qΠk，进行policy的更新。
``
2.代码
import numpy as np
from gridWorldGame import standard_grid, negative_grid,print_values, print_policy
SMALL_ENOUGH = 1e-3
GAMMA = 0.9
ALL_POSSIBLE_ACTIONS = ('U', 'D', 'L', 'R')
def play_game(grid, policy):
start_states = list(grid.actions.keys()) # 将actions输入start ,actions中不包括（0，3） （1，3）的keys
start_idx = np.random.choice(len(start_states)) # 随机选择index
grid.set_state(start_states[start_idx]) #
s = grid.current_state() # 前四句是为了随机选择一个初始policy，赋值给s
states_and_rewards = [(s, 0)]
while not grid.game_over():
a = policy[s]
r = grid.move(a)
s = grid.current_state()
states_and_rewards.append((s,r)) # 一直走直到游戏结束，states_and_rewards里存储了所有步的r
G = 0 #state_value = 0
states_and_returns = [] #
first = True
for s, r in reversed(states_and_rewards): # 就是反转，最后一步为什么要被取消？
if first: # 为什么忽略最后的rewards，按理说到达终点应该会有1的reward
first = False
else:
states_and_returns.append((s, G))
G = r + GAMMA*G
print(states_and_returns)
states_and_returns.reverse()
return states_and_returns
grid = standard_grid()
policy = {
(2, 0): 'U',
(1, 0): 'U',
(0, 0): 'R',
(0, 1): 'R',
(0, 2): 'R',
(1, 2): 'R',
(2, 1): 'R',
(2, 2): 'R',
(2, 3): 'U',
}
V = {}
returns = {}
states = grid.all_states()
for s in states: # 感觉就是为了初始化所有格子的reward为0
if s in grid.actions:
returns[s] = []
else:
V[s] = 0
for t in range(100):
states_and_returns = play_game(grid,policy)
seen_states = set()
for s, G in states_and_returns: # 如果s
if s not in seen_states:
returns[s].append(G)
V[s] = np.mean(returns[s])
seen_states.add(s)
for s in policy.keys():
best_a = None
best_value =float('-inf')
for a in ALL_POSSIBLE_ACTIONS:
grid.set_state(s)
r = grid.move(a)
v = r + GAMMA * V[grid.current_state()]
if v > best_value:
best_value = v
best_a = a
policy[s] = best_a
print("final values:")
print_values(V, grid)
print("final policy:")
print_policy(policy, grid)
代码步骤 1.创建了一个表格，表格里所有的格子的policy都已经确定； 2.play_game()函数，随机选取state以及第一个policy进行游戏，创建episode，返回episode行走路径中的所有reward值(注意每个格子的policy都是确定的，因此，基本等于固定游玩，只是初始位置和初始policy不同）； 3.循环一百次，也就相当于从每次随机从一个格子选取随机策略开始游戏，创建多个episodes，最后取得这个格子进行游戏的state_value平均值。 4.和truncated iteration 一样，最后进行策略更新。
3.代码结果
总结
个人感觉MC Basic代码对于很多state已经确定policy的情况下，且数据量十分少的情况下，还是可以使用的。 和之前两种算法的区别在于，前半部分value iteration和policy iteration都是采用贝尔曼公式来计算的，就是该方法会默认提前知道了条件概率，也就是模型，如p（s，a）：玩家在s选取a动作的概率。而MC Basic则是基于大量数据计算，得到了各个state得state_value。
摘录于：https://github.com/rookiexxj/Reinforcement_learning_tutorial_with_demo/blob/master/monte_carlo_demo.ipynb
https://www.bilibili.com/video/BV1sd4y167NS/