三、序列问题（1）

此前讲述了在某个时间点做一个单一的决定的问题，但许多重要的问题需要做出一系列的决定。序列环境中的最佳决策需要对未来行动和观察序列进行推理。

1. 精确解方法

1.1 马尔可夫决策过程（Markov Decision Processes）

#  Data structure for a MDP
struct MDP
    γ # discount factor
    𝒮 # state space
    𝒜 # action space
    T # transition function
    R # reward function
    TR # sample transition and reward
end

具体概念可参见【RL】Markov decision process马尔可夫决策过程(MDP)

1.2 策略评价

在讨论如何计算最优策略之前，先讨论策略评估，即计算值函数$\mathcal{U}^{\pi}$：$$\begin{align*} \mathcal{U}^{\pi}_{1}(s) & = R(s, \pi(s)), \\ \mathcal{U}^{\pi}_{k+1}(s) & = R(s, \pi(s)) + \gamma \sum_{s^{\prime}} T(s^{\prime} \mid s, \pi(s)) \mathcal{U}^{\pi}_{k}(s^{\prime}).\end{align*}$$ 第二个公式也称为lookahead equation。

function lookahead(𝒫::MDP, U, s, a)
    𝒮, T, R, γ = 𝒫.𝒮, 𝒫.T, 𝒫.R, 𝒫.γ
    return R(s,a) + γ*sum(T(s,a,s′)*U(s′) for s′ in 𝒮)
end
function lookahead(𝒫::MDP, U::Vector, s, a)
    𝒮, T, R, γ = 𝒫.𝒮, 𝒫.T, 𝒫.R, 𝒫.γ
    return R(s,a) + γ*sum(T(s,a,s′)*U[i] for (i,s′) in enumerate(𝒮))
end

function iterative_policy_evaluation(𝒫::MDP, π, k_max)
    𝒮, T, R, γ = 𝒫.𝒮, 𝒫.T, 𝒫.R, 𝒫.γ
    U = [0.0 for s in 𝒮]
    for k in 1:k_max
        U = [lookahead(𝒫, U, s, π(s)) for s in 𝒮]
    end
    return U
end

由于lookahead equation是一个压缩映射的过程，因而该过程收敛，且有Bellman expectation equation $$\mathcal{U}^{\pi}(s) = R(s, \pi(s)) + \gamma \sum_{s^{\prime}} T(s^{\prime} \mid s, \pi(s)) \mathcal{U}^{\pi}(s^{\prime}).$$通过直接求解Bellman expectation equation，无需迭代即可进行政策评估，时间复杂度为$\mathcal{O}(|\mathcal{S}|^{3})$。

function policy_evaluation(𝒫::MDP, π)
    𝒮, R, T, γ = 𝒫.𝒮, 𝒫.R, 𝒫.T, 𝒫.γ
    R′ = [R(s, π(s)) for s in 𝒮]
    T′ = [T(s, π(s), s′) for s in 𝒮, s′ in 𝒮]
    return (I - γ*T′)\R′
end

1.3 值函数策略

根据策略评估的方法，构造最优策略的直接方法是贪婪搜索，即$$\pi(s) = \argmax_{a} \mathcal{U}(s) = \argmax_{a} \left(R(s, a) + \gamma \sum_{s^{\prime}} T(s^{\prime} \mid s, a) \mathcal{U}(s^{\prime})\right).$$如果$\mathcal{U}$是最优值函数，则提取的策略是最优的。

struct ValueFunctionPolicy
    𝒫 # problem
    U # utility function
end

function greedy(𝒫::MDP, U, s)
    u, a = findmax(a->lookahead(𝒫, U, s, a), 𝒫.𝒜)
    return (a=a, u=u)
end

(π::ValueFunctionPolicy)(s) = greedy(π.𝒫, π.U, s).a

另一种方法是使用行动值函数，即Q函数。该函数表示从状态$s$开始，采取行动$a$，然后执行贪婪策略时的预期回报$$Q(s, a) = R(s, a) + \gamma \sum_{s^{\prime}} T(s^{\prime} \mid s, a) \mathcal{U}(s^{\prime}).$$显然，$$\mathcal{U}(s) = \max_{a} Q(s, a),$$进而有$$\pi(s) = \argmax_{a}Q(s, a).$$该方法避免了使用$R$和$T$去提取策略。

策略也可以使用advantage function来表示，该函数量化了采取行动相对于贪婪行动的优势，且定义为$$A(s, a) = Q(s, a) - \mathcal{U}(s).$$

1.4 策略迭代过程

1.4.1 同步迭代

策略迭代是计算最优策略的一种方法。它通过贪婪策略在策略评估（第7.2节）和策略改进之间进行迭代。策略迭代保证在给定任何初始策略的情况下收敛。它虽然可能策略的数量在状态数上是指数级的，但策略迭代通常会快速收敛。

struct PolicyIteration
    π # initial policy
    k_max # maximum number of iterations
end

function solve(M::PolicyIteration, 𝒫::MDP)
    π, 𝒮 = M.π, 𝒫.𝒮
    for k = 1:M.k_max
        U = policy_evaluation(𝒫, π)
        π′ = ValueFunctionPolicy(𝒫, U)
        if all(π(s) == π′(s) for s in 𝒮)
            break
        end
        π = π′
    end
    return π
end

值迭代是策略迭代的一种替代方法，由于其简单性经常被使用。与策略改进不同，值迭代直接更新值函数。常用的值函数初始化为$\mathcal{U}(s) = 0$，$\forall s$，并应用Bellman backup（或Bellman更新）改进值函数：$$ \mathcal{U}_{k+1}(s) = \max_{a} \left(R(s, a + \gamma \sum_{s^{\prime}} T(s^{\prime} \mid s, a) \mathcal{U}_{k}(s^{\prime})\right).$$ 最优策略符合Bellman optimality equation$$ \mathcal{U}^{\ast}(s) = \max_{a} \left(R(s, a + \gamma \sum_{s^{\prime}} T(s^{\prime} \mid s, a) \mathcal{U}^{\ast}(s^{\prime})\right).$$

struct ValueIteration
    k_max # maximum number of iterations
end

function backup(𝒫::MDP, U, s)
    return maximum(lookahead(𝒫, U, s, a) for a in 𝒫.𝒜)
end

function solve(M::ValueIteration, 𝒫::MDP)
    U = [0.0 for s in 𝒫.𝒮]
    for k = 1:M.k_max
        U = [backup(𝒫, U, s) for s in 𝒫.𝒮]
    end
    return ValueFunctionPolicy(𝒫, U)
end

1.4.1 异步迭代

值迭代往往是计算密集型的，因为值函数中的每个条目在每次迭代中都会更新。在异步值迭代中，每次迭代只更新状态的子集。异步值迭代仍然保证收敛于最优值函数，前提是每个状态更新无限次常用的方法为Gauss-Seidel value iteration，但该方法的收敛速度与状态的扫描顺序有关。

struct GaussSeidelValueIteration
    k_max # maximum number of iterations
end

function solve(M::GaussSeidelValueIteration, 𝒫::MDP)
    U = [0.0 for s in 𝒫.𝒮]
    for k = 1:M.k_max
        for (i, s) in enumerate(𝒫.𝒮)
            U[i] = backup(𝒫, U, s)
        end
    end
    return ValueFunctionPolicy(𝒫, U)
end

1.5 线性规划

寻找最优策略的问题可以表示为规划问题 $$\begin{align*}& \max \sum_{s} \mathcal{U}(s) \\ & {\rm s.t. } \mathcal{U}(s) \geq \max_{a} \left(R(s, a + \gamma \sum_{s^{\prime}} T(s^{\prime} \mid s, a) \mathcal{U}_{k}(s^{\prime})\right), \forall s. \end{align*}$$将不等式约束分解为线性约束，即为线性规划问题。

struct LinearProgramFormulation end

function tensorform(𝒫::MDP)
    𝒮, 𝒜, R, T = 𝒫.𝒮, 𝒫.𝒜, 𝒫.R, 𝒫.T
    𝒮′ = eachindex(𝒮)
    𝒜′ = eachindex(𝒜)
    R′ = [R(s,a) for s in 𝒮, a in 𝒜]
    T′ = [T(s,a,s′) for s in 𝒮, a in 𝒜, s′ in 𝒮]
    return 𝒮′, 𝒜′, R′, T′
end

solve(𝒫::MDP) = solve(LinearProgramFormulation(), 𝒫)

function solve(M::LinearProgramFormulation, 𝒫::MDP)
    𝒮, 𝒜, R, T = tensorform(𝒫)
    model = Model(GLPK.Optimizer)
    @variable(model, U[𝒮])
    @objective(model, Min, sum(U))
    @constraint(model, [s=𝒮,a=𝒜], U[s] ≥ R[s,a] + 𝒫.γ*T[s,a,:]⋅U)
    optimize!(model)
    return ValueFunctionPolicy(𝒫, value.(U))
end