首页强化学习

Markov Decision Process

一个Markov Desion Process(MDP) 是一个五元组(S,A,p,r,γ)(\mathcal{S},\mathcal{A},p,r,\gamma), 满足

  • S\mathcal{S} 状态空间，是系统在每个时间步的状态集合
  • A\mathcal{A} 动作空间，是系统在每个状态下可以采取的动作的集合
  • p(s′∣s,a)p(s'\mid s, a) 状态转移概率，从状态ss通过行为aa转移到状态s′s'到概率
  • r:S×A→R=E(R∣s,a)r:\mathcal{S}\times \mathcal{A}\to \mathbb{R}=\mathbb{E}(R\mid s,a) 奖励函数，在状态ss下执行行为aa的全部奖励的期望
  • γ∈[0,1]\gamma\in[0,1] 衰减因子，每个时间步中的奖励衰减

MDP通常可可视化表示为一个有向图，每一个状态为一个点，所有的边的集合为动作空间A\mathcal{A}. 边的权为奖励函数

记

As={a∣s→as′,∀s′∈St+1}{\mathcal{A}_s}=\left\{a\mid s\overset{a}{\to}s', \forall s'\in S_{t+1}\right\}

为状态 ss 的动作空间

Markov Property

Markov特性指当前时间步的状态转移概率、奖励累计与前面时间步的对应量是相互独立的

p(St+1=s′,Rt+1=r∣St,At)=p(St+1=s′,Rt+1=r∣St,At,St−1,At−1,⋯ )p(S_{t+1}=s', R_{t+1}=r\mid S_t,A_t )=p(S_{t+1}=s',R_{t+1}=r\mid S_t,A_t,S_{t-1},A_{t-1},\cdots)

MDP的奖励返回

  • Undiscounted Return
    不考虑衰减因子的总奖励

    Gt=∑k=0T−t−1Rt+k+1G_t = \sum_{k=0}^{T-t-1}R_{t+k+1}

  • Discounted Return

    Gt=∑k=0T−t−1γkRt+k+1G_t = \sum_{k=0}^{T-t-1}\gamma^k R_{t+k+1}

  • Average Return

    Gt=1T−t−1∑k=0t+k+1Rt+k+1G_t = \frac{1}{T-t-1}\sum_{k=0}^{t+k+1}R_{t+k+1}

Agent Policy 智能体策略

Goal of RL Agent

To find a behavior policy that maximises the expected return GtG_t

智能体策略的精神是寻找到最大的奖励

Policy 智能体策略

  • 宏观(全局定义)
    由智能体主导的全局决策法则。在 MDP 的有向图结构中，它表现为从状态空间向动作空间发出的概率分配（边权）。它在面对环境给定的庞大图网络时，通过裁剪和概率倾斜，决定了智能体在图中游走的整体行为倾向。
  • 微观(逐点定义)
    智能体在状态ss下执行某一动作aa的概率

策略数学表达为

π:S→P(A)⊂[0,1],π(a∣s)=p(At=a∣St=s)\pi:\mathcal{S}\to P(\mathcal{A})\subset [0,1],\quad \pi(a\mid s)=p(A_t=a\mid S_t=s)

如果存在可学习的参数 θ\theta，则记作

πθ(a∣s)\pi_\theta(a\mid s)

对于离散动作空间，策略满足

∑a∈Asπθ(a∣s)=1\sum_{a\in \mathcal{A}_s} \pi_\theta(a\mid s)=1

对于连续动作空间，策略满足

∫a∈Asπθ(a∣s) da=1\int_{a\in\mathcal{A}_s}\pi_\theta(a\mid s)\,\mathrm{d}a=1

Value Function 价值函数

vπ(s)=E(Gt∣St=s,π)v_\pi(s)=\mathbb{E}(G_t\mid S_t=s,\pi)

Q Function

Q Function 指的是在状态St=sS_t=s，执行动作At=aA_t=a下的价值期望函数

qπ(s,a)=E(Gt∣St=s,At=a,π)=E(∑k=0∞γkRt+k+1∣St=s,At=a,π)q_\pi (s,a)=\mathbb{E}(G_t\mid S_t=s,A_t=a,\pi)=\mathbb{E}\left(\sum_{k=0}^\infty\gamma^k R_{t+k+1}\mid S_t=s,A_t=a,\pi\right)

根据全概率公式，价值函数满足

vπ(s)=∑a∈Asπ(a∣s)qπ(s,a)v_\pi(s)=\sum_{a\in \mathcal{A}_s} \pi(a\mid s)q_\pi(s,a)

Optimal Value Function 最优化价值函数

Optimal state-value function 最优状态价值函数，是在所有策略中的最大状态价值函数

v∗(s)=max⁡πvπ(s)v^\ast(s)=\max_{\pi} v_\pi (s)

Optimal action-value function 最优动作价值函数,是在所有策略中的最大动作价值函数

q∗(s,a)=max⁡πqπ(s,a)q^\ast(s,a)=\max_{\pi}q_\pi (s,a)

Claim: 解决一个 MDP 的本质就是寻找最优策略. 一旦求解出最优价值函数，我们便称该马尔可夫决策过程（MDP）得到了解决（Solved）

在此基础上，我们定义策略的偏序关系

π′≥π⟺∀s∈S, vπ′(s)≥vπ(s)\pi'\geq \pi \Longleftrightarrow \forall s\in\mathcal{S},\, v_{\pi'}(s)\geq v_\pi(s)

根据Zorn Lemma,最优策略总存在

Optimal policy 最优策略

最优策略π∗\pi^\ast满足

∀π∈Π,π≤π∗\forall \pi \in \Pi, \pi\leq \pi^\ast

Bellman Equation

Action Value Function 的时间步展开

qπ(s,a)=E(Gt∣ST=s,At=a,π)=E(Rt+1+γvπ(St+1)∣St=s,At∈π(St),π)=∑r∈Rt+1∑s′∈St+1p(r,s′∣s,a)(r+γvπ(s′))=∑a∈A(s)π(a∣s)∑r∈Rt+1∑s′∈St+1p(r,s′∣s,a)(r+γ∑a′∈A(s′)(π(a′∣s′)qπ(s′,a′)))\begin{aligned} q_\pi(s,a)&=\mathbb{E}(G_t\mid S_T=s,A_t=a,\pi)\\ &=\mathbb{E}\left(R_{t+1}+\gamma v_\pi(S_{t+1})\mid S_t=s, A_t\in\pi(S_t),\pi\right)\\ &=\sum_{r\in R_{t+1}}\sum_{s'\in \mathcal{S}_{t+1}}p(r,s'\mid s,a)(r+\gamma v_\pi(s'))\\ &=\sum_{a\in \mathcal{A}(s)}\pi(a\mid s)\sum_{r\in R_{t+1}}\sum_{s'\in \mathcal{S}_{t+1}}p(r,s'\mid s,a)(r+\gamma \sum_{a'\in \mathcal{A}(s')}(\pi(a'\mid s')q_\pi(s',a'))) \end{aligned}

Value Function 的时间步展开

vπ(s)=∑aπ(a∣s)qπ(s,a)=∑a∈A(s)π(a∣s)∑r∈Rt+1∑s′∈St+1p(r,s′∣s,a)(r+γvπ(s′))\begin{aligned} v_\pi(s)&=\sum_{a}\pi(a\mid s)q_\pi(s,a)\\ &=\sum_{a\in \mathcal{A}(s)}\pi(a\mid s)\sum_{r\in R_{t+1}}\sum_{s'\in \mathcal{S}_{t+1}}p(r,s'\mid s,a)(r+\gamma v_\pi(s')) \end{aligned}

Bellman Expectation Equation Bellman期望方程刻画了状态价值函数与行为价值函数的递归关系。
对于给定的MDP， M=(S,A,p,r,γ)\mathcal{M}=(\mathcal{S},\mathcal{A},p,r,\gamma), 对于任意策略π\pi，价值函数满足

vπ(s)=∑a∈A(s)π(a∣s)∑r∈Rt+1∑s′∈St+1p(r,s′∣s,a)(r+γvπ(s′))qπ(s,a)=∑a∈A(s)π(a∣s)∑r∈Rt+1∑s′∈St+1p(r,s′∣s,a)(r+γ∑a′∈A(s′)(π(a′∣s′)qπ(s′,a′)))\begin{align} v_\pi(s) &= \sum_{a\in \mathcal{A}(s)}\pi(a\mid s)\sum_{r\in R_{t+1}}\sum_{s'\in \mathcal{S}_{t+1}}p(r,s'\mid s,a)(r+\gamma v_\pi(s')) \tag{1} \\ q_\pi(s,a) &= \sum_{a\in \mathcal{A}(s)}\pi(a\mid s)\sum_{r\in R_{t+1}}\sum_{s'\in \mathcal{S}_{t+1}}p(r,s'\mid s,a)(r+\gamma \sum_{a'\in \mathcal{A}(s')}(\pi(a'\mid s')q_\pi(s',a'))) \tag{2} \end{align}