奖励(reward)

RtR_t 来表示反馈给agent的奖励,类于一个信号表示对agent在第 tt 步的好坏评价。

而强化学习基于的就是如下的奖励假设:

所有目标都可以描述成最大化预期累积奖励。

历史与状态(history and state)

我们把从第 11 步到第 tt 步行动,观察,奖励所形成的序列称为历史,即 HtH_t :

Ht=A1,O1,R1,,At,Ot,RtH_t = A_1, O_1, R_1, \cdots , A_t, O_t, R_t

下一步的决定就是来自于历史。但是由于其数据量过大,我们往往通过agent的状态来决定下一步的行为,也就是一个关于历史的函数,即:

St=f(Ht)S_t = f(H_t)

对于agent以及环境会存在多种状态:

我们将agent历史中所有有用的信息称为马尔科夫状态(Markov state)。

我们定义一个状态 StS_t 有马尔可夫性质当且仅当:

P[St+1St]=P[St+1S1,,St]\mathbb{P}[S_{t+1}|S_t] = \mathbb{P}[S_{t+1}|S_1,\cdots,S_t]

这就意味着未来的状态只需考虑当前状态,因为当前状态包含了之前的所有状态。

H1:tStHt+1:H_{1:t}\to S_t \to H_{t+1:\infty}

The environment state SteS_t ^e and history HtH_t is Markov.

Full Observable Environment & Partially Observable Environment

Full Observable Environment或许应该译为“完全可观察环境”?这是一种理想的强化学习环境,具有如下特性:

Ot=Sta=SteO_t = S_t ^a = S_t ^e

即我们观察到的状态就是环境的状态。这种环境下的机器学习是Markov decision process (MDP).

同理,Partially Observable Environment指agent无法观察到全部的环境状态。该环境下的机器学习称为partially observable Markov decision process (POMDP).

Agent主要组成部分

一个RL agent可能由以下几个函数组成:

  • Policy: agent的行为函数
  • Value function: state或者action的价值
  • Model: 感知agent所处环境的变化

Policy

Policy是一个从状态到行为的对应关系。

确定策略(Deterministic policy): a=π(s)a = \pi(s)

随机策略(Stochastic policy): π(as)=P[At=aSt=s]\pi(a|s) = \mathbb{P}[A_t = a|S_t = s]

Value function

Value function是一个对于未来的奖励的预测,用来评估当前状态的好坏。

vπ(s)=Eπ[Rt+1+γRt+2+γ2Rt+3+St=s]v_\pi(s) = \mathbb{E_\pi}[R_{t + 1} + \gamma R_{t + 2} + \gamma ^2 R_{t + 3} + \cdots | S_t = s]

其中 γ\gamma 是一个小于等于 11 的权值,因为我们对近期的奖励更看重。

Model

Model会对环境的下一步变化进行预测。

Transitions: P\mathcal{P} 预测下一个状态
Rewards: R\mathcal{R} 预测下一次(即时)奖励

Pssa=P[S=sS=s,A=a]Rsa=E[RS=s,A=a]\mathcal{P}^a_{ss'} = \mathbb{P}[S' = s'|S = s, A = a]\\ \mathcal{R}^a_s = \mathbb{E}[R|S = s, A = a]

MDP

状态转移矩阵(State Transition Matrix)

我们定义agent从一个状态到另一个状态的转移概率(state transition probability) Pss\mathcal{P_{ss'}}

Pss=P[St+1=sSt=s]\mathcal{P_{ss'}} = \mathbb{P}[S_{t + 1} = s'|S_t = s]

状态转移矩阵是所有状态间转移概率的矩阵:

P=[P11P1nPn1Pnn]\mathcal{P} = \begin{bmatrix} \mathcal{P_{11}} & \cdots & \mathcal{P_{1n}} \\ \vdots & \ddots & \vdots \\ \mathcal{P_{n1}} & \cdots & \mathcal{P_{nn}} \end{bmatrix}

马尔可夫过程(Markov Process)

马尔可夫过程是满足马尔可夫性质的随机过程,其由二元组 $ \left \langle \mathcal{S,P} \right \rangle$ 构成,其中:

  • S\mathcal{S} 是有限状态集合
  • P\mathcal{P} 是状态转移概率矩阵

例如对于一个学生上课的过程,我们可以有这样一个状态转移概率矩阵:
屏幕截图 2023-03-14 154424.png
在这个例子中无论状态转移的回合有多长,最后都会到达Sleep的状态,由此我们可以写如下的episodes,即马尔科夫链:

  • C1 \to C2 \to C3 \to Pass \to Sleep
  • C1 \to C2 \to C3 \to Pub \to C2 \to C3 \to Pass \to Sleep

马尔可夫奖励过程(Markov Reward Process)

马尔可夫奖励过程是一个四元组 S,P,R,γ\left \langle \mathcal{S,P,R,\gamma} \right \rangle 其中:

  • S\mathcal{S} 是有限状态集合
  • P\mathcal{P} 是状态转移概率矩阵
  • R\mathcal{R} 是奖励函数, Rs=E[Rt+1St=s]\mathcal{R}_s = \mathbb{E}[R_{t + 1}|S_t = s]
  • γ\gamma 是衰减因子(discounted factor), γ[0,1]\gamma \in [0,1]

将前文中的例子加上奖励函数即是MRP:
屏幕截图 2023-07-18 155101.png

我们用 GtG_t 来表示return,即强化学习经过 tt 步后的总奖励:

Gt=Rt+1+γRt+2+=k=0γkRt+k+1G_t = R_{t + 1} + \gamma R_{t + 2} + \cdots = \sum_{k = 0} ^{\infty} \gamma ^k R_{t + k + 1}

贝尔曼方程(Bellman Equation)

我们有:

Gt=Rt+1+γRt+2+γ2Rt+3+=Rt+1+(γRt+2+γ2Rt+3+)=Rt+1+γGt+1\begin{align*} G_t &= R_{t + 1} + \gamma R_{t + 2} + \gamma^2 R_{t + 3} + \cdots \\ &=R_{t + 1} + (\gamma R_{t + 2} + \gamma^2 R_{t + 3} + \cdots) \\ &= R_{t + 1} + \gamma G_{t + 1} \\ \end{align*}

于是对于价值函数,我们有递归的贝尔曼方程:

v(s)=E[GtSt=s]=E[Rt+1+γGt+1St=s]=E[Rt+1+γv(St+1)St=s]\begin{align*} v(s) &= \mathbb{E}[G_t|S_t = s] \\ &= \mathbb{E}[R_{t + 1} + \gamma G_{t + 1}|S_t = s] \\ &= \mathbb{E}[R_{t + 1} + \gamma v(S_{t + 1})|S_t = s] \end{align*}

我们可以把贝尔曼方程写成矩阵形式:

v=R+γPvv = \mathcal{R} + \gamma \mathcal{P}v

其中 vv 是一个价值函数的列向量。
于是我们有:

v=R+γPv(1γP)v=Rv=(1γP)1R\begin{align*} v &= \mathcal{R} + \gamma \mathcal{P}v \\ (1 - \gamma \mathcal{P})v &= \mathcal{R} \\ v &= (1 - \gamma \mathcal{P})^{-1}\mathcal{R} \end{align*}

因此,我们可以在 O(n3)\mathcal{O}(n^3) 的时间复杂度内计算出 vv

马尔可夫决策过程(Markov Decision Process)

马尔可夫决策过程是一个五元组 S,A,P,R,γ\left \langle \mathcal{S,A,P,R,\gamma} \right \rangle 其中:

  • S\mathcal{S} 是有限状态集合
  • A\mathcal{A} 是决策过程中动作的有限集合
  • P\mathcal{P} 是状态转移概率矩阵, Pss=P[St+1=sSt=s,At=a]\mathcal{P_{ss'}} = \mathbb{P}[S_{t + 1} = s'|S_t = s, A_t = a]
  • R\mathcal{R} 是奖励函数, Rsa=E[Rt+1St=s,At=a]\mathcal{R}_s ^a = \mathbb{E}[R_{t + 1}|S_t = s, A_t = a]
  • γ\gamma 是衰减因子, γ[0,1]\gamma \in [0,1]

对于一个MDP S,A,P,R,γ\left \langle \mathcal{S,A,P,R,\gamma} \right \rangle 和一个给定的策略 π\pi ,我们可以发现:

  • 状态的序列是一个马尔可夫链 S,Pπ\langle \mathcal{S,P^\pi} \rangle
  • 状态和奖励的序列可以构成一个MRP S,Pπ,Rπ,γ\left \langle \mathcal{S,P^{\pi},R^{\pi},\gamma} \right \rangle
  • 其中:

Pssπ=aAπ(as)PssaRsπ=aAπ(as)Rsa\mathcal{P}^{\pi}_{ss'} = \sum_{a\in A} \pi(a|s)\mathcal{P}^a_{ss'} \\ \mathcal{R}^{\pi}_{s} = \sum_{a\in A} \pi(a|s)\mathcal{R}^a_{s} \\

由于在MDP中存在策略,我们对于一个给定的策略定义如下两个价值函数:

状态-价值函数:

vπ(s)=Eπ[GtSt=s]v_{\pi}(s) = \mathbb{E}_{\pi}[G_t|S_t = s]

行为-价值函数:

qπ(s,a)=Eπ[GtSt=s,At=a]q_{\pi}(s, a) = \mathbb{E}_{\pi}[G_t|S_t = s, A_t = a]

利用MRP中贝尔曼方程的思路,可以得到:

vπ(s)=Eπ[Rt+1+γvπ(St+1)St=s]qπ(s,a)=Eπ[Rt+1+γqπ(St+1,At+1)St=s,At=a]v_{\pi}(s) = \mathbb{E}_{\pi}[R_{t + 1} + \gamma v_{\pi}(S_{t + 1})|S_t = s] \\ q_{\pi}(s, a) = \mathbb{E}_{\pi}[R_{t + 1} + \gamma q_{\pi}(S_{t + 1}, A_{t + 1})|S_t = s, A_t = a]

同理,也可以写出矩阵形式的贝尔曼方程:

vπ=Rπ+γPπvπ=(1γPπ)1Rπ\begin{align*} v_{\pi} &= \mathcal{R}^{\pi} + \gamma \mathcal{P}^{\pi}v_{\pi} \\ &= (1 - \gamma \mathcal{P}^{\pi})^{-1}\mathcal{R}^{\pi} \end{align*}

更进一步,我们考虑 vπv_{\pi}qπq_{\pi} 之间的关系。因为状态的价值可以理解为当前状态所有行为的平均价值。于是我们有:

vπ(s)=aAπ(as)qπ(s,a)v_{\pi}(s) = \sum_{a\in A}\pi (a|s)q_{\pi}(s, a)

同理,行为价值可以理解为该行为之后的所有状态的平均价值:

qπ(s,a)=Rsa+γsSPssavπ(s)q_{\pi}(s, a) = \mathcal{R}^a_s + \gamma \sum_{s' \in S} \mathcal{P}^a_{ss'} v_{\pi}(s')

那么我们将这两个式子相互代入,我们可以得到另一种递归计算价值函数的方法:

vπ=aAπ(as)(Rsa+γsSPssavπ(s))qπ(s,a)=Rsa+γsSPssaaAπ(as)qπ(s,a)v_{\pi} = \sum_{a\in \mathcal{A}}\pi (a|s) \left ( \mathcal{R}^a_s + \gamma \sum_{s' \in \mathcal{S}} \mathcal{P}^a_{ss'} v_{\pi}(s') \right ) \\ q_{\pi}(s, a) = \mathcal{R}^a_s + \gamma \sum_{s' \in \mathcal{S}} \mathcal{P}^a_{ss'} \sum_{a'\in \mathcal{A}}\pi (a'|s')q_{\pi}(s', a')

最优价值函数(Optimal Value Function)

我们定义最优价值函数是价值函数中的最大值,用 $v_{*}(s) $ 和 q(s)q_*(s) 来表示:

v(s)=maxπvπ(s)q(s,a)=maxπqπ(s,a)v_*(s) = \max_{\pi} v_{\pi}(s) \\ q_*(s, a) = \max_{\pi} q_{\pi}(s, a)

利用前文中的例子,加上 q(s,a)q_*(s, a) 后如下图所示:
屏幕截图 2023-07-20 113345.png

最优策略(Optimal Policy)

为了定义最优策略,我们先定义策略的偏序:

π>π if vπ(s)vπ(s),s\pi > \pi' \ \text{if}\ v_{\pi}(s) \geq v_{\pi'}(s), \forall s

那么对于任何一个MDP,存在一个策略 π\pi_* 大于其他任何策略,称为最优策略。

并且显然有,最优价值函数中的策略一定是最优策略。即:

vπ(s)=v(s)qπ(s,a)=q(s,a)v_{\pi_*}(s) = v_*(s) \\ q_{\pi_*}(s, a) = q_*(s, a)

因此,我们可以通过寻找使得 q(s,a)q_*(s, a) 最大的action来得到 π\pi_*

π(as)={1,if a=arg maxaAq(s,a)0,otherwise\pi_*(a|s) = \begin{cases} 1, & \text{if}\ a = \argmax_{a\in \mathcal{A}} q_*(s, a) \\ 0, & \text{otherwise} \end{cases}

贝尔曼最优方程(Bellman Optimality Equation)

按照上文中贝尔曼方程的思想,可以考虑 vv_*qq_* 之间的关系,我们有:

v(s)=maxaq(s,a)q(s,a)=Rsa+γsSPssav(s)v_*(s) = \max_a q_*(s, a) \\ q_*(s, a) = \mathcal{R}_s^a + \gamma \sum_{s' \in \mathcal{S}}\mathcal{P}^a_{ss'}v_*(s')

从而将两者互相带入,得到贝尔曼最优方程:

v(s)=maxaRsa+γsSPssav(s)q(s,a)=Rsa+γsSPssamaxaq(s,a)v_*(s) = \max_{a} \mathcal{R}_s^a + \gamma \sum_{s' \in \mathcal{S}}\mathcal{P}^a_{ss'}v_*(s') \\ q_*(s, a) = \mathcal{R}_s^a + \gamma \sum_{s' \in \mathcal{S}}\mathcal{P}^a_{ss'}\max_{a'} q_*(s', a')

感觉差不多了,写的好杂,之后会慢慢联系起来的。