前言

在之前的博文中，有详细说明MDP。本文用一个简单易懂的赌徒问题，作为例子，说明如何实现MDP的相关算法。如何求解出最优策略。

1. 问题描述

赌徒下注猜测一系列抛硬币的结果。

如果正面朝上，则他获得该次下注的钱。如果背面朝上，则失去这一次下注的钱。

当赌徒获利100元，或者输光的时候，游戏结束。

2. 问题建模

该问题可以表述为非折扣的分幕式有限MDP。

状态S：赌徒的赌资 S $\in${1,2,3,…99}

动作Action： 赌徒下注的金额 a$\in${0, 1, … , min(s, 100-s)}

收益reward： 赌徒达到100美元终止状态，收益为1；其余均为0

$p_h$: 表示抛硬币正面朝上的概率

所以，状态价值函数，表征的是在每个状态S下，赌徒获胜的概率。而策略 $\pi$是赌资到赌注的映射。

最优策略需要最大化状态价值函数，也就是最大化赌徒获胜的概率。

3. 实现

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


# goal
GOAL = 100

# all states, including state 0 and state 100
STATES = np.arange(GOAL + 1)

# 正面朝上的概率
HEAD_PROB = 0.4


def gamblers_problem():
    # state value
    state_value = np.zeros(GOAL + 1)
    state_value[GOAL] = 1.0

    sweeps_history = []

    # value iteration
    while True:
        old_state_value = state_value.copy()
        sweeps_history.append(old_state_value)

        for state in STATES[1:GOAL]:
            # get possilbe actions for current state
            actions = np.arange(min(state, GOAL - state) + 1)
            action_returns = []
            for action in actions:
                action_returns.append(
                    HEAD_PROB * state_value[state + action] + (1 - HEAD_PROB) * state_value[state - action])
            new_value = np.max(action_returns)
            state_value[state] = new_value
        delta = abs(state_value - old_state_value).max()
        if delta < 1e-9:
            sweeps_history.append(state_value)
            break

    # compute the optimal policy
    policy = np.zeros(GOAL + 1)
    for state in STATES[1:GOAL]:
        actions = np.arange(min(state, GOAL - state) + 1)
        action_returns = []
        for action in actions:
            action_returns.append(
                HEAD_PROB * state_value[state + action] + (1 - HEAD_PROB) * state_value[state - action])

        # round to resemble the figure in the book, see
        policy[state] = actions[np.argmax(np.round(action_returns[1:], 5)) + 1]

    plt.figure(figsize=(10, 20))

    plt.subplot(2, 1, 1)
    for sweep, state_value in enumerate(sweeps_history):
        plt.plot(state_value, label='sweep {}'.format(sweep))
    plt.xlabel('Capital')
    plt.ylabel('Value estimates')
    plt.legend(loc='best')

    plt.subplot(2, 1, 2)
    plt.scatter(STATES, policy)
    plt.xlabel('Capital')
    plt.ylabel('Final policy (stake)')

    plt.savefig('./images/figure_4_3.png')
    plt.close()


if __name__ == '__main__':
    gamblers_problem()

核心代码分析：

值迭代部分：

    while True:
        old_state_value = state_value.copy()
        sweeps_history.append(old_state_value)

        for state in STATES[1:GOAL]:
            # get possilbe actions for current state
            actions = np.arange(min(state, GOAL - state) + 1)
            action_returns = []
            for action in actions:
                action_returns.append(
                    HEAD_PROB * state_value[state + action] + (1 - HEAD_PROB) * state_value[state - action])
            new_value = np.max(action_returns)
            state_value[state] = new_value
        delta = abs(state_value - old_state_value).max()
        if delta < 1e-9:
            sweeps_history.append(state_value)
            break

状态的value最开始除了s=100外都初始化为0

每个状态都有 状态数值个action可以选择。

对于状态集合中的每个state的每个action（两个for循环遍历），都计算出来<state, action> 获得的收益，按照贝尔曼最优方程进行更新状态价值（即选择最优的action使得当前状态收益最大）。

$$v_{\pi }(s)=\underset{a}{\max }\sum _{s^{\prime },r}p(s^{\prime },r|s,a)[r+\gamma v_{\pi }(s^{\prime })]$$

最后设置阈值delta，满足条件之后，退出价值迭代的循环。

最优策略部分：

    policy = np.zeros(GOAL + 1)
    for state in STATES[1:GOAL]:
        actions = np.arange(min(state, GOAL - state) + 1)
        action_returns = []
        for action in actions:
            action_returns.append(
                HEAD_PROB * state_value[state + action] + (1 - HEAD_PROB) * state_value[state - action])

        policy[state] = actions[np.argmax(np.round(action_returns[1:], 5)) + 1]

首先初始化所有的policy为0

然后同样对于每个state的每个action，求出对应的价值，然后从中选取价值最大的action，作为赌注。

注意：

1. 为消除state_value中不确定因素的影响，我们将对求得的action_returns保留小数点后五位数字。

2. 当对应当前赌资State同时可以选取多个action获得相同的获胜概率的时候，我们采取保守策略，选择赌注最少(action值最小)的Action进行下注。

3. 因为赌徒下注赌资为0的话，没有意义，我们只选择[1:]部分的赌注作为有效action

4. 结果分析

<1> $p_h$=0.1

当$p_h$为0.1的时候，经过10轮值迭代之后，找到最优状态价值函数。

<2> $p_h$=0.3

当$p_h$为0.5的时候，经过15轮值迭代之后，找到最优状态价值函数。

<3> $p_h$=0.5

当$p_h$为0.5的时候，经过13轮值迭代之后，找到最优状态价值函数。

按照最小的原则，

<4> $p_h$=0.7

当$p_h$为0.7的时候，经过93轮值迭代之后，找到最优状态价值函数。

4. 总结

1. 当$p_h>=0.5$时，最优策略都可以设定为每次只下注 1；当$p_h<0.5$时，其中就有一些不一样的情况，比如在赌资为 25， 50，75的时刻。
2. 观察下图绘制出来的最优价值函数曲线与不同的p的对比图，我们更能看出一些问题。当$p_h<0.5$时，在几个可以一步到位成功的关键处，对应赌资的价值估计都会明显高于周围。这也解释了最终的最优策略的形状。但是当$p_h>=0.5$时，p越大成功概率越高，对应的价值估计越高。