强化学习（Reinforcement Learning,RL）中有智能体（Agent）和环境（Environment）。智能体与环境进行交互（Interaction），智能体观察到环境的一个状态（State），对环境执行一个动作（Action），得到环境的一个奖励（Reward），环境进入下一个状态，不断重复，见强化学习交互图。环境最初处于初始状态，过程中状态不断发生变化，直到环境进入一个终止状态（Terminal State）。整个过程是智能体与环境交互的序列（Sequence）决策过程。强化学习的目标是最大化智能体在环境中获得的最终累积奖励，称为回报（Return）。这里只考虑交互是有限的情况，称为有限期（Finite Horizon）。

“强化学习交互图”

马尔可夫决策过程

强化学习假设上述序列决策过程是一个随机过程，由马尔可夫决策过程（Markov Decision Process,MDP）描述。

MDP={S,A,P,R,γ}\begin{equation} MDP = \{\mathcal{S},\mathcal{A},P,R,\gamma\} \end{equation}

其中：

  • S\mathcal{S}：状态空间，环境中所有可能的状态集合。
  • A\mathcal{A}：动作空间，智能体在环境中可以执行的所有可能的动作集合。
  • PP：状态转移概率函数，描述在状态ss下执行动作aa后转移到下一个状态s′s'的概率，即P(s′∣s,a)P(s'|s,a)，其满足马尔可夫性。
  • RR：奖励函数，描述在状态ss下执行动作aa后获得的奖励，即R(s,a)R(s,a)。
  • γ\gamma：折扣因子（衰减系数）。

马尔可夫过程中产生的序列可以表示为：

S0,A0,R1,S1,A1,…,St,At,Rt+1,…RT,STS_0, A_0, R_1, S_1, A_1, \ldots ,S_{t} , A_{t}, R_{t+1}, \ldots R_{T}, S_{T}

称为轨迹（Trajectory）。其中，StS_t表示时间步tt的状态，AtA_t表示时间步tt的动作，Rt+1R_{t+1}表示在时间步tt执行动作后获得的奖励。

轨迹数据中的累积的奖励或回报为：

Gt=Rt+1+γRt+2+γ2Rt+3+⋯\begin{equation} G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots \end{equation}

环境决定了状态转移概率P(s′∣s,a)P(s'|s,a)和奖励函数R(s,a)R(s,a)。状态转移概率和奖励函数称为模型（Model）。智能体决定的是策略（Policy），即策略函数π:S×A→[0,1]\pi:\mathcal{S} \times \mathcal{A} \rightarrow [0,1]，定义为条件概率分布P(A=a∣S=s)P(A=a \mid S=s)。

状态价值函数（State Value Function）：V:S↦RV: \mathcal{S} \mapsto \mathbb{R}，其中Vπ(s)=Eπ[Gt∣St=s]V_{\pi}(s) = \mathbb{E}_{\pi}[G_t \mid S_t = s]表示智能体在时刻tt 处于状态ss 时，按照策略π\pi 行动所获得的回报的期望。价值函数衡量了某个状态的好坏程度，反映了智能体从当前状态出发能够为目标完成带来多大“好处”。

动作价值函数（Action-value Function）：q:S×A↦Rq: \mathcal{S} \times \mathcal{A} \mapsto \mathbb{R}，其中 qπ(s,a)=Eπ[Gt∣St=s,At=a]q_{\pi}(s, a) = \mathbb{E}_{\pi}[G_t \mid S_t = s, A_t = a]表示智能体在时刻tt处于状态ss并选择动作aa后，按照策略π\pi 行动所获得的回报的期望。通过最大化动作价值函数，智能体可得到最佳奖励。

于是我们给出强化学习的问题：

给定一个马尔可夫决策过程MDP={S,A,P,R,γ}MDP = \{\mathcal{S},\mathcal{A},P,R,\gamma\}，学习一个最优策略π∗\pi^*，使得对于所有状态s∈Ss \in \mathcal{S}，Vπ∗(s)≥Vπ(s)V_{\pi^*}(s) \geq V_{\pi}(s)，其中π\pi是任意其他策略。

贝尔曼方程

贝尔曼方程（Bellman Equation）也被称作动态规划方程（Dynamic Programming Equation），是强化学习中的一个重要工具，用于描述状态价值函数和动作价值函数之间的关系.

我们已知

Vπ(s)=Eπ[Rt+1+γGt+2+γ2Gt+3+⋯∣St=s]=∑a∈Aπ(s,a)qπ(s,a)qπ(s,a)=Eπ[Rt+1+γGt+2+γ2Gt+3+⋯∣St=s,At=a]=R(s′∣s,a)+γ∑s′∈SP(s,a,s′)Vπ(s′)\begin{align} & \begin{aligned} V_{\pi}(s) & = \mathbb{E}_{\pi}[R_{t+1} + \gamma G_{t+2} + \gamma^2 G_{t+3} + \cdots \mid S_t = s]\\ & = \sum_{a \in \mathcal{A}} \pi(s,a)q_{\pi}(s,a) \end{aligned}\\ & \begin{aligned} q_{\pi}(s, a) = \mathbb{E}_{\pi}[R_{t+1} + \gamma G_{t+2} + \gamma^2 G_{t+3} + \cdots \mid S_t = s, A_t = a]\\ = R(s' \mid s,a) + \gamma \sum_{s' \in \mathcal{S}} P(s,a,s')V_{\pi}(s') \end{aligned} \end{align}

则代入可得

Vπ(s)=∑a∈Aπ(s,a)∑s′∈SP(s′∣s,a)[R(s,a,s′)+γVπ(s′)]qπ(s,a)=∑s′∈SP(s′∣s,a)[R(s,a,s′)+γ∑a′∈Aπ(s′,a′)qπ(s′,a′)]\begin{align} V_{\pi}(s) & = \sum_{a \in \mathcal{A}} \pi(s,a) \sum_{s' \in \mathcal{S}}P(s' \mid s,a)[R(s,a,s') + \gamma V_{\pi}(s')]\\ q_{\pi}(s, a) & = \sum_{s' \in \mathcal{S}}P(s' \mid s,a) \left[R(s,a,s') + \gamma \sum_{a' \in \mathcal{A}} \pi(s',a')q_{\pi}(s',a')\right] \end{align}

可知两个价值函数取值与时间都没有关系。状态价值函数只与策略π\pi、在策略π\pi下的从某个状态转移到其后续状态所获得的回报以及之后所得的回报有关；动作价值函数只与瞬时奖励和下一步的状态和动作有关。

贝尔曼方程描述了价值函数的递归关系。在实际中，需要计算得到最优策略以指导智能体在当前状态如何选择一个可获得最大回报的动作。求解最优策略的一种方法就是去求解最优的状态价值函数或最优的动作价值函数（即基于价值方法，value-based approach）。一旦找到了最优的状态价值函数或动作价值函数，自然而然也就找到了最优策略。当然，在强化学习中还有基于策略（policy-based）和基于模型（model-based）等不同方法。具体的来说，强化学习分为模型无关（model-free）和模型相关（model-based）两大类方法。而上述所说的基于价值的方法和基于策略的方法都属于模型无关方法。