第一章：Reinforcement Learning Basic Concepts

1. 基础元素：以 Grid World 为例

我们使用一个 $3 \times 3$ 的格子世界作为贯穿本章的示例。

1.1 State

• 定义：Agent 相对于 Environment 的位置或状态。
• State Space $\mathcal{S}$：所有可能 State 的集合。
  • $\mathcal{S} = \{s_i\}_{i=1}^9 = \{s_1, s_2, \dots, s_9\}$。

1.2 Action

• Action Space $\mathcal{A}$：某个 State 下 Agent 可以采取的所有 Action 的集合。
  • $\mathcal{A}(s_i) = \{a_1, a_2, a_3, a_4, a_5\}$。

1.3 State Transition

• 定义：Agent 采取 Action 后，从当前 State 移动到下一个 State 的过程。
  • $s_1 \xrightarrow{a_2} s_2$。
• 边界与障碍：
  • Boundary：撞墙后反弹回原位（如 $s_1 \xrightarrow{a_1} s_1$）。
  • Forbidden Area：
    1. Accessible：可进入但受罚（本课程设定）。
    2. Inaccessible：有墙阻隔，保持原地。
• 表示方法：
  1. Tabular Representation：仅适用于 Deterministic 环境。
  2. State Transition Probability：适用于 Stochastic 环境。
     • $p(s'|s, a)$

1.4 Policy

• 定义：指导 Agent 在某个 State 下采取什么 Action。
• 数学表示：条件概率分布 $\pi(a|s)$。
  • $\sum_{a} \pi(a|s) = 1$
• 分类：
  1. Deterministic Policy：$\pi(a|s) = 1$ （特定动作）。
  2. Stochastic Policy：$\pi(a|s) \in [0, 1]$ （概率分布）。

1.5 Reward

• 定义：执行 Action 后 Environment 反馈的实数值。
• 作用：
  • Encouragement：Positive Reward。
  • Punishment：Negative Reward。
• 数学表示：$p(r|s, a)$。
• 设定：
  • $r_{bound} = -1$
  • $r_{forbid} = -1$
  • $r_{target} = +1$

2. 交互过程与评估

2.1 Trajectory

• 定义：State-Action-Reward chain。
• $s_1 \xrightarrow{a_2, r=0} s_2 \xrightarrow{a_3, r=0} s_5 \dots$

2.2 Return

• Reward ($R$)：单步即时反馈。
• Return ($G$)：Trajectory 上所有 Reward 的总和。
• Discounted Return：引入 Discount Rate $\gamma \in [0, 1)$。
  • $G_t = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}$
  • $\gamma \approx 0$：Short-sighted（重视近期）。
  • $\gamma \approx 1$：Far-sighted（重视远期）。

2.3 Episode

• Episode：有限步的任务，通常在达到 Terminal State 后停止。
• 任务处理：
  1. Absorbing State：进入后不再离开，Reward 为 0。
  2. Normal State：可继续行动，反复获得 Reward（本课程采用，将 Episodic 任务转化为 Continuing 任务）。

3. Markov Decision Process (MDP)

MDP 是 RL 的数学框架，包含以下核心要素：

3.1 Sets

1. State Space $\mathcal{S}$
2. Action Space $\mathcal{A}(s)$
3. Reward Set $\mathcal{R}(s, a)$

3.2 Dynamics / Model

1. State Transition Probability：$p(s'|s, a)$
2. Reward Probability：$p(r|s, a)$

3.3 Policy

• $\pi(a|s)$：在 State $s$ 选择 Action $a$ 的概率。

3.4 Markov Property

• Memoryless Property：未来状态仅取决于当前 State 和 Action。
  • $p(s_{t+1} | s_t, a_t, \dots) = p(s_{t+1} | s_t, a_t)$
  • $p(r_{t+1} | s_t, a_t, \dots) = p(r_{t+1} | s_t, a_t)$

4. MDP vs MP

• MDP (Markov Decision Process)：包含 Action 选择。
  • $p(s'|s, a)$
• MP (Markov Process)：不含 Action，状态按固定概率转移。
  • $p(s'|s)$
• 关系：MDP 固定 Policy 后退化为 MP。
  • $p(s'|s) = \sum_{a} p(s'|s, a) \pi(a|s)$