马尔科夫决策过程(MDP)：赌徒问题

问题描述:

一个赌徒玩一个游戏，输赢由抛硬币的结果来决定，每一局游戏开始，都必须拿出部分的赌资下注。如果硬币头朝上，他赌多少赢多少(double)。如果头朝下，就输掉赌注。当赌徒达到100美元的目标时，或者缺钱时，游戏结束。

问题抽象

问题可以看作一个离散的马尔可夫决策过程：

• $s$ : state，赌徒当前持有的赌资， s ∈ S = { 0 , 1 , 2 , . . . 99 } s\in \mathcal{S}=\{0,1,2,...99\} s∈S={0,1,2,...99}
• $a$ : action，赌徒每次下注的金额， a ∈ A = { 1 , 2 , . . . m i n ( s , 100 − s ) } a\in \mathcal{A}=\{1,2,...min(s,100-s)\} a∈A={1,2,...min(s,100−s)}
• $r$ : reward，只有达到目标时为1，其他均为0， r ∈ R = { 0 , 1 } r \in \mathcal{R}=\{0,1\} r∈R={0,1}
• $\gamma$ : discount，$\gamma =1$
• $p_h$ : 硬币头朝上的概率

求解策略

方法一 ：Policy Iteration

1. Initialization:
   • $V(s)\in Rand\pi (s)\in \mathcal{A}(s)arbitrarilyforalls\in \mathcal{S}$
2. Policy Evaluation:
   • Loop:
     • $\Delta \leftarrow 0$
     • Loop for each $s\in \mathcal{S}$:
       • $v\leftarrow V(s)$
       • $V(s)\leftarrow {\sum }_{s^{\prime },r}p(s^{\prime },r|s,\pi (s))[r+\gamma V(s^{\prime })]$
       • $\Delta \leftarrow max(\Delta ,|v-V(s)|)$
   • until $\Delta <=\theta$ (a small positive number determining the accuracy of estimation)
3. Policy Improvement:
   • policy-stable $\leftarrow$ true
   • For each $s\in S$:
     • old-action $\leftarrow \pi (s)$
     • $\pi (s)\leftarrow \underset{a}{\mathrm{argmax}}{\sum }_{s^{\prime },r}p(s^{\prime },r|s,a)[r+\gamma V(s^{\prime })]$
     • If old-action $\ne \pi (s)$,then policy=stable $\leftarrow$ false
   • If policy-stable,then stop and return $V\approx v_{\ast }and\pi \approx {\pi }_{\ast }$; esle go to 2

import numpy as np
import seaborn as sns
import matplotlib.pyplot as plt

class PolicyIteration:
    def __init__(self, goal = 100, proba_h = 0.4, theta=1e-9, gamma = 1):
        self.ph = proba_h
        self.gamma = gamma
        self.goal = goal
        self.theta = theta
        self.states = np.arange(self.goal + 1)
        self.state_values = np.zeros(self.goal + 1)
        self.state_values[self.goal] = 1.0
        self.policy = np.zeros(self.goal + 1)
        self.sweeps_history = []
        
    def policy_evaluation(self):
        while True:
            old_state_values = self.state_values.copy()
            self.sweeps_history.append(old_state_values)
            for s in self.states[1:self.goal]:
                actions = np.arange(min(s, self.goal - s))+1
                action_returns = []
                for a in actions:
                    ret = self.ph * (self.gamma * self.state_values[s + a]) + \
                          (1 - self.ph) * (self.gamma * self.state_values[s - a])
                    action_returns.append(ret)
                self.state_values[s] = np.mean(action_returns)
            delta = abs(self.state_values - old_state_values).max()
            if delta <= self.theta:
                break
    
    def policy_improvement(self):
        policy_stable = True
        for s in self.states[1:self.goal]:
            actions = np.arange(min(s, self.goal - s))+1
            old_a = self.policy[s]
            action_returns = []
            for a in actions:
                ret = self.ph * (self.gamma * self.state_values[s + a]) + \
                      (1 - self.ph) * (self.gamma * self.state_values[s - a])
                action_returns.append(ret)
            argmax_a = actions[np.argmax(np.round(action_returns,5))]
            self.policy[s] = argmax_a
            if policy_stable and argmax_a != old_a:
                policy_stable = False
        return policy_stable

值函数和最优策略 $P_h=0.4$

方法二 ：Value Iteration

1. Initialization:
   • $V(s)\in Rand\pi (s)\in \mathcal{A}(s)arbitrarilyforalls\in \mathcal{S}$
2. Truncated Policy Evaluation:
   • Loop:
     • $\Delta \leftarrow 0$
     • Loop for each $s\in \mathcal{S}$:
       • $v\leftarrow V(s)$
       • $V(s)\leftarrow \underset{a}{\max }{\sum }_{s^{\prime },r}p(s^{\prime },r|s,\pi (s))[r+\gamma V(s^{\prime })]$
       • $\Delta \leftarrow max(\Delta ,|v-V(s)|)$
   • until $\Delta <=\theta$ (a small positive number determining the accuracy of estimation)
3. Optimal policy,$\pi \approx {\pi }_{\ast }$:
   • $\pi (s)=\underset{a}{\mathrm{argmax}}{\sum }_{s^{\prime },r}p(s^{\prime },r|s,a)[r+\gamma V(s^{\prime })]$

class ValueIteration:
    def __init__(self, goal = 100, proba_h = 0.4, theta=1e-9, gamma = 1):
        self.ph = proba_h
        self.gamma = gamma
        self.goal = goal
        self.theta = theta
        self.states = np.arange(self.goal + 1)
        self.state_values = np.zeros(self.goal + 1)
        self.state_values[self.goal] = 1.0
        self.policy = np.zeros(self.goal + 1)
        self.sweeps_history = []
        
    def truncated_policy_evaluation(self):
        while True:
            old_state_values = self.state_values.copy()
            self.sweeps_history.append(old_state_values)
            for s in self.states[1:self.goal]:
                actions = np.arange(min(s, self.goal - s))+1
                action_returns = []
                for a in actions:
                    ret = self.ph * (self.gamma * self.state_values[s + a]) + \
                          (1 - self.ph) * (self.gamma * self.state_values[s - a])
                    action_returns.append(ret)
                self.state_values[s] = np.max(action_returns)   # max_a
            delta = abs(self.state_values - old_state_values).max()
            if delta <= self.theta:
                break
    
    def optimal_policy(self):
        for s in self.states[1:self.goal]:
            actions = np.arange(min(s, self.goal - s))+1
            old_a = self.policy[s]
            action_returns = []
            for a in actions:
                ret = self.ph * (self.gamma * self.state_values[s + a]) + \
                      (1 - self.ph) * (self.gamma * self.state_values[s - a])
                action_returns.append(ret)
            argmax_a = actions[np.argmax(np.round(action_returns,5))]
            self.policy[s] = argmax_a

值函数和最优策略 $P_h=0.4$

值函数和最优策略 $P_h=0.55$

结果对比

相同胜率下：$P_h=0.4$

上述结果中，在相同的胜率下，策略迭代和值迭代得到了不同的最优策略，两个策略之间约有1/4是完全重合的,${\pi }_{pi}$,呈现出分段式的激进与保守。${\pi }_{vi}$则是周期性的激进与保守。

关键结论：

1. Truncated Policy Evaluation方法值函数收敛的速度更快，减少遍历全部状态的次数。
2. Policy Iteration 和 Value Iteration 的主要区别：
   • PI：$v_{k+1}(s)=E[R_{t+1}+\gamma v_k(S_{t+1})|S_t=s,A_t=a]$,所有可能动作的期望
   • VI：$v_{k+1}(s)=\underset{a}{\max }E[R_{t+1}+\gamma v_k(S_{t+1})|S_t=s,A_t=a]$,最大动作的期望