这里直接融合了first visit和every visit，当选择every visit，策略更新使用stochastic的epsilon greedy；选择first visit，策略更新使用greedy。
理论基础：
需要说明：
1. 由于我发现agent大多数时候更倾向于呆在原地，因为走到终点的reward太小，而走到forbidden或者boundary的reward又是很大的负数，因此呆在原地是长远考虑。因此我增加了r_stay，当模型决定留在原地就给一定的惩罚。在env.py中添加即可。同时注意测试时r_boundary和r_forbidden不应该设置的太小。
2. 在env.py的step方法中需要调整，可以允许agent进入forbidden区域。
if not (0 <= ni < self.size and 0 <= nj < self.size): next_state = self.state_id(i,j) else: next_state = self.state_id(ni,nj)from collections import defaultdict import numpy as np from env import GridWorldEnv from utils import drow_policy class MonteCarloPolicyIteration(object): def __init__(self, env: GridWorldEnv, gamma=0.9, samples=1, mode="first visit"): self.env = env self.action_space_size = self.env.num_actions # 上下左右原地 self.reward_space_size = self.env.reward_space_size # 执行每个动作的reward self.state_space_size = self.env.num_states self.reward_list = self.env.reward_list self.gamma = gamma self.samples = samples self.mode = mode self.policy = np.ones((self.state_space_size, self.action_space_size)) / self.action_space_size self.state_value = np.zeros((self.env.size, self.env.size)) self.qvalues = np.zeros((self.state_space_size, self.action_space_size)) self.returns = np.zeros((self.state_space_size, self.action_space_size)) # 必须初始化为0，不是zeros_like self.nums = np.zeros((self.state_space_size, self.action_space_size)) def solve(self, iterations=20, epsilon=0.1): ''' :param iterations: 迭代的次数 :param epsilon: epsilon greedy：[0,1] epsilon=0：greedy，就选择best action；epsilon=1:stochastic，选择所有action的概率相同 ''' for i in range(iterations): for _ in range(self.samples): # 随机选择一个非终点状态作为起始状态,确保所有的状态都能被充分访问 non_terminal_states = [i for i in range(self.state_space_size) if i not in self.env.terminal] s = np.random.choice(non_terminal_states) a = np.random.choice(self.action_space_size, p=self.policy[s]) # 按policy采样 episode = self.generate_episodes(s, a) self.update_q_from_episode(episode) for s in range(self.state_space_size): if s in self.env.terminal: self.policy[s] = np.eye(self.action_space_size)[4] else: best_a = np.argmax(self.qvalues[s]) if self.mode=="every visit": # 如果是first visit，很多(s,t)可能被访问了很多次，但是却只用它做了一次action value的估计 # epsilon greedy self.policy[s] = epsilon / self.action_space_size # 给其他action小概率 self.policy[s, best_a] += 1 - epsilon # 给最有可能的action大概率 elif self.mode=="first visit": # 实际对应epsilon=0的情况 self.policy[s]=np.eye(self.action_space_size)[best_a] self.state_value = np.sum(self.policy * self.qvalues, axis=1).reshape(self.env.size, self.env.size) def generate_episodes(self, start_state, start_action, max_steps=200): ''' :param start_state: 当前状态的state_id :param start_action: 当前动作 :return: [(state_id, action，reward),(...)] ''' episode = [] state = start_state action = start_action for _ in range(max_steps): next_state, reward, done = self.env.step(state, action) episode.append((state, action, reward)) if done: break state = next_state action = np.random.choice(self.action_space_size, p=self.policy[state]) # 从[0,action_space_size)随机选一个，每个action的概率为policy[state] return episode def update_q_from_episode(self, episode): G = 0 visit = set() for s, a, r in reversed(episode): # 如果直接使用reversed(episode)就会同时把tuple内部也反转了 G = r + self.gamma * G if self.mode == "first visit": if (s, a) not in visit: self.returns[s, a] += G self.nums[s, a] += 1 self.qvalues[s, a] = self.returns[s, a] / self.nums[s, a] elif self.mode == "every visit": self.returns[s, a] += G self.nums[s, a] += 1 self.qvalues[s, a] = self.returns[s, a] / self.nums[s, a] else: raise Exception("Invalid mode") if __name__ == '__main__': env = GridWorldEnv( size=5, forbidden=[(1, 2),(3,3)], terminal=[(4,4)], r_boundary=-1, r_other=-0.04, r_terminal=1, r_forbidden=-1, r_stay=-0.1 ) vi = MonteCarloPolicyIteration(env=env, gamma=0.9, samples=10, mode="every visit") vi.solve(iterations=10000, epsilon=0.3) # 只有mode="every visit"才需要传入epsilon print("\n state value: ") print(vi.state_value) drow_policy(vi.policy, env)对于相同的配置，iteration=100、1000、10000时，策略分别是
可以发现，iteration越大，策略越优。
由于stochastic，因此相同的配置运行多次结果也很大概率不同，大多数时候agent在进行一些exploration，因此看起来策略并不是最好的。因此epsilon greedy实际上是牺牲了最优性，换取了更多的exploration，epsilon越小，越接近最优greedy，epsilon越大，跑的时间也越长。
