强化学习复习笔记#1

基本概念

Agent（智能体）: 学习者和决策者
Reward（奖励）: 智能体尝试最大化的一个数值
Environment （环境）: 智能体之外与奖励有关的一切

智能体和环境不断地进行交互：

要对于这种决策过程进行建模，我们使用马尔可夫决策过程（Markov Decision Process, MDP）。

马尔可夫决策过程

用元组 \((\mathcal{S}, \mathcal{A}, \mathcal{R}, \mathcal{P}, \gamma)\) 来描述，其中按顺序分别是状态（states），动作（actions），奖励（rewards），转移概率（transition probabilities）和折现率（discount rate）。

转移概率 \(p \in \mathcal{P}\)：

\[
p(s’, r | s, a) \doteq \mathrm{Pr} \{ S_t = s’, R_t = r | S_{t - 1} = s, A_{t - 1} = a \}
\]

也就是说呢，这个转移概率的定义即是在状态 \(s\) 下，进行动作 \(a\)，能够进入状态 \(s’\) 并且获得奖励 \(r\) 的概率。不难发现，这个概率只是依赖于紧接着的之前的状态和动作，更早的不在考量中。

The marginal probablity of the reward \(r\):

\[
p(r | s, a) = \sum_{s’ \in \mathcal{S}}p(s’, r | s, a)
\]

The marginal probablity of the next state \(s’\):

\[
p(s’ | s, a) = \sum_{r \in \mathcal{R}}p(s’, r | s, a)
\]

状态-行动对的预期回报：

\[
r(s, a) \doteq \mathbb{E}[R_t | S_{t-1} = s, A_{t-1} = a] = \sum_{r \in \mathcal{R}}r \sum_{s’ \in \mathcal{S}}p(s’, r | s, a)
\]

MDP 的返回：

\[
G_t \doteq R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}
\]

为啥会有一个折现率 \(\gamma\) 呢？这玩意儿表达的意思是，未来奖励对我们来说没有现在眼前奖励重要，所以我们用这么一个因子来削弱未来奖励的影响。假如 \(\gamma = 0\)，那么我们的智能体非常短视，只能看到眼前一步的奖励。类似的，假如 \(\gamma \rightarrow 1\)，那么我们的智能体是比较远视的。

递推形式：

\[
G_t \doteq R_{t+1} + \gamma G_{t+1}
\]

对于持续任务（continuing task），即智能体和环境的交互持续不断的任务来说，如上所述，我们有 \( G_t \doteq R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1} \)。

而对于非持续任务（episodic task），即存在一个明确的结束的任务来说，我们有 \( G_t \doteq R_{t+1} + R_{t+2} + R_{t+3} + \dots + R_T \)。

策略：

Stochastic policy: \(\pi (a | s):\mathcal{S} \mapsto [0, 1]\)，即 \(\pi (\cdot | s)\) 是一个在 \(\mathcal{A}\) 上的概率分配，可用于探索和数据收集
Determinictic policy: \(\pi : \mathcal{S} \mapsto \mathcal{A}\)，即 \(a = \pi (s)\)

价值函数：

State-value function: 从状态 \(s\) 开始，并在之后按照策略 \(\pi\) 进行行动的预期返回值

\[
v_{\pi} (s) \doteq \mathbb{E}_{\pi}[G_t | S_t = s] = \mathbb{E}_{\pi}\left[\sum_{k=0}^{\infty} \gamma^k R_{t+k+1} \bigg| S_t = s\right]
\]
Action-value function: 从状态 \(s\) 开始，进行动作 \(a\)，并在之后按照策略 \(\pi\) 进行行动的预期返回值

\[
q_{\pi} (s, a) \doteq \mathbb{E}_{\pi}[G_t | S_t = s, A_t = a] = \mathbb{E}_{\pi}\left[\sum_{k=0}^{\infty} \gamma^k R_{t+k+1} \bigg| S_t = s, A_t = a\right]
\]

价值函数能让我们衡量一个策略 \(\pi\) 的好坏，并且可用于策略表现的提升。

贝尔曼方程：

\[
\begin{equation}
\begin{split}
v_{\pi} (s) & \doteq \mathbb{E}_{\pi}[G_t | S_t = s] \\
& = \mathbb{E}_{\pi}[R_{t+1} + \gamma G_{t+1} | S_t = s] \\
& = \sum_a \pi (a | s) \sum_{s’} \sum_r p(s’, r | s, a) \left[r + \gamma \mathbb{E}_{\pi}[G_{t+1} | S_{t+1} = s’]\right] \\
& = \sum_a \pi (a | s) \sum_{s’, r} p(s’, r | s, a) \left[r + \gamma v_\pi (s’)\right],\mbox{ for all } s \in \mathcal{S}
\end{split}
\end{equation}
\]

current state value = one step (immediate) reward + discounted value of the next state

贝尔曼最优方程

Optimal state-value function:

\[
v_* (s) \doteq \underset{\pi}{\mathrm{max}} \ v_\pi (s) \mbox{ for all } s \in \mathcal{S}
\]

Optimal action-value function:

\[
q_* (s, a) \doteq \underset{\pi}{\mathrm{max}} \ q_\pi (s, a) \mbox{ for all } s \in \mathcal{S} \mbox{ and } a \in \mathcal{A}
\]

\[
v_* (s) = \underset{a \in \mathcal{A}(s)}{\mathrm{max}} \ q_{\pi_*} (s, a) \mbox{ for all } s \in \mathcal{S}
\]

\[
v_* (s) = \underset{a}{\mathrm{max}} \ \sum_{s’, r} p(s’, r | s, a)[r + \gamma v_* (s’)]
\]

\[
q_* (s, a) = \sum_{s’, r} p(s’, r | s, a)[r + \gamma \underset{a’}{\mathrm{max}} \ q_* (s’, a’)]
\]

我们可以使用 \( v_{*} \) 和 \( q_{*} \) 来计算最优策略：

对于 state-value function：

\[
\begin{split}
a^* & = \underset{a}{\mathrm{argmax}} \ \mathbb{E} [R + \gamma v_* (S’)] \\
& = \underset{a}{\mathrm{argmax}} \ \sum_{s’, r} p(s’, r | s, a)[r + \gamma v_* (s’)]
\end{split}
\]

对于 action-value function，更简单，无需 transition probabilities：

\[
a^* = \underset{a}{\mathrm{argmax}} \ q_* (s, a)
\]

最终我们把问题的关键放在解决贝尔曼最优方程上面，只要解决了它，自然能得出最优的决策过程。