Reinforcement Learning强化学习系列之三：MC Control

本文主要是介绍Reinforcement Learning强化学习系列之三：MC Control，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

引言

前面一篇文章中说到了MC prediction，主要介绍的是如何利用采样轨迹的方法计算Value函数，但是在强化学习中，我们主要想学习的是Q函数，也就是计算出每个state对应的action以及其reward值，在这篇文章中，将会介绍。

MC control with epsilon-greedy

这一部分将会介绍基于 $\epsilon-greedy$ 方法，所谓 $\epsilon-greedy$ 方法，就是对于当前策略，我们以 $1-epsilon$ 的概率选择当前策略所要执行的动作A，以 $\epsilon$ 的概率随机执行其他的动作，对于动作状态空间有 $|A|$ 个的状态，其动作执行策略是：

π (s t a t e) = ⎧ ⎩ ⎨ ⎪ ⎪ 1 - ϵ + ϵ | A | a = π (s t a t e) ϵ | A | a! = π (s t a t e)

$\pi(state)=\left\{ \begin{aligned} & 1-\epsilon+\frac{\epsilon}{|A|} \quad a =\pi(state) \\ & \frac{\epsilon}{|A|} \quad a!=\pi(state) \\ \end{aligned} \right.$
同样，对于上一篇的21点游戏，我们将MC Prediction中的策略替换成现在所使用的

ϵ−greedy ϵ − g r e e d y $\epsilon-greedy$ 策略，那么其算法改变如下：
这里写图片描述

为此我们将上一篇文章中的策略迭代代码换成如下：

def epsilon_greedy_policy(Q,observation,nA,epsilon):best_action = np.argmax(Q[observation])A = np.ones(nA,dtype=np.float32)*epsilon/nAA[best_action] += 1-epsilonreturn Adef MC_Control_with_epsilon_greedy(env,episode_nums,discount_factor=1.0, epsilon=0.1):env = Blackjack()Q = defaultdict(lambda:np.zeros(env.nA))return_sum=defaultdict(float)return_count=defaultdict(float)for i_episode in range(1,1+episode_nums):env._reset()state = env.observation()episode=[]if i_episode % 1000 == 0:print("\rEpisode {}/{}.".format(i_episode, episode_nums))sys.stdout.flush()for i in range(100):A = epsilon_greedy_policy(Q,state,env.nA,epsilon)probs = Aaction = np.random.choice(np.arange(env.nA),p=probs)next_state,reward,done = env._step(action)episode.append((state,action,reward))if done:breakelse:state = next_stateseperate_episode = set([(tuple(x[0]), x[1]) for x in episode])for state,action in seperate_episode:for idx,e in enumerate(episode):if e[0]==state and e[1]==action:first_visit_idx = idxbreakpair = (state,action)G = sum([e[2]*(discount_factor**i) for i,e in enumerate(episode[first_visit_idx:])])return_sum[pair]+=Greturn_count[pair]+=1.0Q[state][action]=return_sum[pair]*1.0/return_count[pair]return Q

同样我们迭代500000次，根据所得到的Q函数，计算出每个state的最佳reward值：

for state, actions in Q.items():action_value = np.max(actions)V[state] = action_value

我们将Value绘制出来：
这里写图片描述

Off-Policy MC control with epsilon-greedy

上面一小节显示的是On-Policy的策略评估方法，所谓On-Policy，也就是执行的策略和要更新的策略是一个策略，而与之相反的是，Off-Policy表示的是执行的策略和更新的策略不是一个策略，在Off-Policy方法里面，执行的策略称之为behavior-policy，而要更新的策略称之为target-policy,如何根据behavior-policy来更新target-policy呢，这里涉及的一个知识点就是重要性采样，所谓重要性采样，就是当我们计算

\int f (x) p (x) d x

$\int f(x)p(x)dx$ 的时候，可以引入一个新的已知的概率分布

p(x) p ( x ) $p(x)$ ，并将其改写为：

\int f ( x ) p ( x ) p (x) d x

$\int \frac{f(x)}{p(x)}p(x)dx$ 上式可以看成

f(x)p(x) f ( x ) p ( x ) $\frac{f(x)}{p(x)}$ 在

p(x) p ( x ) $p(x)$ 上的期望值，而

f(x)p(x) f ( x ) p ( x ) $\frac{f(x)}{p(x)}$ 就可以看作是一个重要性的权重，对于任意的behavior-policy，在

t t $t$ 时刻，后面的采样序列

A_{t}, S_{t + 1}, A_{t + 1}, . . ., S_{T}

$A_t,S_{t+1},A_{t+1},...,S_T$ 的概率是：

P (A t, S t + 1, A t + 1, . . ., S T | S t, A t : T - 1 \sim π) = π (A t | S t) p (S t + 1 | S t, A t) π (A t + 1 | S t + 1) . . . p (S T | S T - 1, A T - 1) = \prod k + t T - 1 π (A k | S k) p (S k + 1 | s k, A k)

$P(A_t,S_{t+1},A_{t+1},...,S_T | S_t,A_{t:{T-1}} \sim \pi) = \pi(A_t|S_t)p(S_{t+1}|S_t,A_t)\pi(A_{t+1}|S_{t+1})...p(S_T|S_{T-1,A_{T-1}}) = \prod_{k+t}^{T-1}\pi(A_k|S_k)p(S_{k+1}|s_k,A_k)$
对于target-policy其计算方式一致，那么target-policy而言，使用behavior-policy采样的比例为：

\prod T - 1 k + t π ( A k | S k ) p ( S k + 1 | s k , A k ) \prod T - 1 k + t b ( A k | S k ) p ( S k + 1 | s k , A k ) = \prod k = t T - 1 π ( A k | S k ) b ( A k | s k )

$\frac{\prod_{k+t}^{T-1}\pi(A_k|S_k)p(S_{k+1}|s_k,A_k)}{\prod_{k+t}^{T-1}b(A_k|S_k)p(S_{k+1}|s_k,A_k)}=\prod_{k=t}^{T-1}\frac{\pi(A_k|S_k)}{b(A_k|s_k)}$
这个值记为

ρt:T(t)−1 ρ t : T ( t ) − 1 $\rho_{t:T(t)-1}$
那么在使用behavior-policy的时候，target-policy的Value值可以计算为：

V (s t a t e) = \sum t \in τ ( s ) ρ t : T ( t ) - 1 G t | τ ( s t a t e ) |

$V(state) = \frac{\sum_{t\in \tau(s)}\rho_{t:T(t)-1}G_t}{|\tau(state)|}$ ，其中

τ(s) τ ( s ) $\tau(s)$ 表示behavior-policy采样的轨迹，

τ(state) τ ( s t a t e ) $\tau(state)$ 表示的是state在episode中出现的次数。我们可以进一步将这个式子改写成带权重的重要性采样的方法：

V (s t a t e) = \sum t \in τ ( s ) ρ t : T ( t ) - 1 G t \sum t \in τ ( s ) ρ t : T ( t ) - 1

$V(state) = \frac{\sum_{t\in \tau(s)}\rho_{t:T(t)-1}G_t}{\sum_{t \in \tau(s)}\rho_{t:T(t)-1}}$

这样我们就可以根据behavior-policy更新得到target-policy的值函数，同理我们也可以得到target-policy的Q函数。我们将上面式子中的 $\rho_{t:T(t)-1}$ 替换成 $W$ ，那么上式子可以表示为：

V_{n} = \frac{\sum_{k = 1}^{n - 1} W_{k} G_{k}}{\sum_{k = 1}^{n - 1} W_{k}} 2 \leq n

$V_n = \frac{\sum_{k=1}^{n-1}W_kG_k}{\sum_{k=1}^{n-1}W_k} \quad 2 \leq n$
通过上面式子可以得到如下关系：

V n + 1 = V n + W n C n [G n - V n]

$V_{n+1} = V_n +\frac{W_n}{C_n}[G_n - V_n]$
其中

Cn+1=Cn+Wn+1 C n + 1 = C n + W n + 1 $C_{n+1} = C_n+W_{n+1}$
由此可以得出Off-policy的更新方法：
这里写图片描述

将MC Control的策略代码修改为：

def sample_policy(Q,observation,nA):A = np.ones(nA,dtype=np.float32)/nAreturn Adef Off_policy_MC_Control(env,episode_nums,discount_factor=1.0):env = Blackjack()Q = defaultdict(lambda:np.zeros(env.nA))target_policy = defaultdict(float)return_count=defaultdict(float)for i_episode in range(1,1+episode_nums):env._reset()state = env.observation()episode=[]prob_b=[]if i_episode % 1000 == 0:print("\rEpisode {}/{}.".format(i_episode, episode_nums))sys.stdout.flush()for i in range(100):A = sample_policy(Q,state,env.nA)probs = Aaction = np.random.choice(np.arange(env.nA),p=probs)next_state,reward,done = env._step(action)episode.append((state,action,reward))prob_b.append(probs[action])if done:breakelse:state = next_stateseperate_episode = set([(tuple(x[0]), x[1]) for x in episode])G =0.0W =1prob_b=prob_b[::-1]for idx,eps in enumerate(episode[::-1]):state,action,reward  = epspair=(state,action)G = discount_factor*G+rewardreturn_count[pair]+=WQ[state][action]+=W*1.0/return_count[pair]*(G-Q[state][action])target_policy[state] = np.argmax(Q[state])if target_policy[state]!=action:breakW = W*1.0/prob_b[idx]return Q