强化学习（Reinforcement Learning，RL）是机器学习的一个重要分支，研究智能体（Agent）如何在环境中通过试错学习最优行为策略，以最大化累积奖励。与监督学习需要标注数据不同，强化学习通过与环境的交互获取反馈信号（奖励或惩罚），逐步学习最优决策策略。

强化学习的核心思想源于行为心理学中的操作性条件反射理论。斯金纳的实验表明，动物会通过试错学习，将特定行为与奖励或惩罚关联起来，从而形成行为模式。强化学习将这一思想形式化为数学框架，使机器能够自主学习复杂任务。

强化学习系统由两个核心要素组成：智能体（Agent）和环境（Environment）。智能体是决策的制定者，它观察环境状态，选择并执行动作，接收环境的反馈（奖励和下一状态）。环境是智能体所处的外部世界，它接收智能体的动作，根据状态转移规则改变状态，并返回奖励信号。

智能体与环境之间的交互遵循马尔可夫决策过程（Markov Decision Process，MDP）框架。在每个时间步$t$，智能体观察到当前状态$s_t$，根据策略选择动作$a_t$。环境响应动作，转移到新状态$s_{t+1}$，并返回奖励$r_{t+1}$。这个交互过程持续进行，形成一个轨迹（trajectory）：$s_0, a_0, r_1, s_1, a_1, r_2, s_2, ...$

强化学习的优化目标是最大化累积折扣奖励（discounted cumulative reward）：

$$G_t = r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} + ... = \sum_{k=0}^{\infty} \gamma^k r_{t+k+1}$$

其中$\gamma \in [0,1]$是折扣因子，用于权衡即时奖励和未来奖励的重要性。当$\gamma$接近0时，智能体更关注即时奖励；当$\gamma$接近1时，智能体更重视长期回报。

强化学习与其他机器学习范式的关键区别在于：没有监督信号告诉智能体应该采取什么动作，只有环境的评估反馈（奖励）。智能体必须主动探索环境，发现哪些动作能够带来更高的长期回报。这种试错学习的特性使得强化学习特别适合那些难以定义明确目标但容易评估结果的任务。

强化学习具有几个显著的特点，这些特点既是其优势所在，也是其面临的主要挑战：

试错探索（Trial-and-Error Exploration）：智能体必须通过尝试不同的动作来发现好的策略，这意味着需要平衡探索（Exploration）与利用（Exploitation）。探索是尝试新的、未知的动作以发现更好的策略；利用是选择当前认为最优的动作以获得即时奖励。过度探索会浪费时间和资源；过度利用可能陷入局部最优。如何平衡探索与利用是强化学习的核心难题之一。

延迟奖励（Delayed Reward）：在许多任务中，智能体的动作不会立即产生奖励，而是影响后续状态，奖励可能在多步之后才能获得。例如，在国际象棋中，只有在游戏结束时才能获得最终奖励。智能体必须能够信用分配（Credit Assignment），确定哪些动作对最终奖励有贡献。

时间序列决策：强化学习涉及序列决策问题，当前动作会影响未来的状态和可选动作。这种时间上的相关性使得问题比独立同分布（i.i.d.）的预测问题复杂得多。

环境动态未知：在大多数强化学习场景中，环境的动态（状态转移概率和奖励函数）是未知的或过于复杂而难以建模。智能体必须通过采样经验来学习环境模型或直接学习最优策略。

高维状态空间：现实世界问题往往具有巨大的状态空间（如围棋有$10^{170}$种可能局面），不可能对每个状态单独处理。需要泛化能力，将学习到的知识迁移到未访问过的状态。

强化学习已经在多个领域取得了突破性成果：

游戏AI：强化学习在游戏领域取得了最瞩目的成就。DeepMind的DQN算法在Atari游戏中超越了人类玩家；AlphaGo使用蒙特卡洛树搜索与深度强化学习结合，击败了世界围棋冠军；OpenAI Five在Dota 2游戏中击败了世界冠军队伍；AlphaStar在星际争霸II中达到了宗师级别。

机器人控制：强化学习使机器人能够学习复杂的运动技能，如行走、奔跑、抓取物体、开门等。通过仿真到现实（Sim-to-Real）迁移技术，在虚拟环境中训练的策略可以迁移到真实机器人上。

推荐系统：强化学习被用于个性化推荐，通过考虑用户的长期参与度而非即时点击率来优化推荐策略。

自动驾驶：强化学习用于车辆的路径规划、决策制定和控制器优化。

资源调度：在数据中心、云计算和通信网络中，强化学习用于动态资源分配和负载均衡。

金融交易：强化学习用于投资组合管理、高频交易策略和风险管理。

自然语言处理：强化学习被用于对话系统、文本摘要和机器翻译，以优化长期对话质量而非单个回合的响应。

马尔可夫决策过程是强化学习的数学基础，为序列决策问题提供了一个严谨的建模框架。一个MDP由五元组$\langle S, A, P, R, \gamma \rangle$定义：

1. 状态空间$S$：环境所有可能状态的集合。状态$s_t \in S$包含了智能体做决策所需的全部信息。
2. 动作空间$A$：智能体所有可能动作的集合。动作可以是离散的（如“左移”、“右移”）或连续的（如电机的扭矩值）。
3. 状态转移概率$P$：$P(s'|s,a)$表示在状态$s$执行动作$a$后转移到状态$s'$的概率。在确定性环境中，$P$退化为确定性函数。
4. 奖励函数$R$：$R(s,a,s')$或$R(s,a)$表示在状态$s$执行动作$a$（并转移到$s'$）后获得的即时奖励。
5. 折扣因子$\gamma$：$\gamma \in [0,1]$用于计算累积折扣奖励。

马尔可夫性质是MDP的核心假设：给定当前状态，未来状态的条件概率分布与历史状态无关。数学表达为：

$$P(s_{t+1}|s_t, a_t, s_{t-1}, a_{t-1}, ..., s_0, a_0) = P(s_{t+1}|s_t, a_t)$$

马尔可夫性质意味着状态$s_t$包含了预测未来所需的全部信息。在实际应用中，原始观察可能不满足马尔可夫性质，需要通过状态设计或循环神经网络来近似。

策略（Policy）$\pi$定义了智能体在给定状态下选择动作的方式。策略可以是确定性的$\pi(s) = a$，也可以是随机的$\pi(a|s) = P(A_t=a|S_t=s)$。

强化学习的目标是找到最优策略$\pi^*$，使得从任意状态出发的期望累积奖励最大化。

价值函数评估状态或状态-动作对的“好坏”程度：

状态价值函数$V^{\pi}(s)$：从状态$s$开始，遵循策略$\pi$的期望累积奖励：

$$V^{\pi}(s) = \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]$$

动作价值函数$Q^{\pi}(s,a)$：在状态$s$执行动作$a$后，再遵循策略$\pi$的期望累积奖励：

$$Q^{\pi}(s,a) = \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]$$

两者之间的关系：$V^{\pi}(s) = \sum_a \pi(a|s) Q^{\pi}(s,a)$，$Q^{\pi}(s,a) = \sum_{s',r} P(s',r|s,a)[r + \gamma V^{\pi}(s')]$

最优价值函数：$V^*(s) = \max_{\pi} V^{\pi}(s)$，$Q^*(s,a) = \max_{\pi} Q^{\pi}(s,a)$

贝尔曼方程（Bellman Equation）是强化学习中最重要的等式，它建立了价值函数的递归关系。

贝尔曼期望方程表达了价值函数的自洽性：

$$V^{\pi}(s) = \sum_a \pi(a|s) \sum_{s',r} P(s',r|s,a)[r + \gamma V^{\pi}(s')]$$

$$Q^{\pi}(s,a) = \sum_{s',r} P(s',r|s,a)\left[r + \gamma \sum_{a'} \pi(a'|s') Q^{\pi}(s',a')\right]$$

贝尔曼最优方程描述了最优价值函数的性质：

$$V^*(s) = \max_a \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 \max_{a'} Q^*(s',a')]$$

贝尔曼最优方程的含义是：最优策略下的价值等于立即奖励加上下一状态的最优价值的折扣值。

从最优价值函数可以导出最优策略：

$$\pi^*(s) = \arg\max_a Q^*(s,a) = \arg\max_a \sum_{s',r} P(s',r|s,a)[r + \gamma V^*(s')]$$

这意味着，如果知道了$Q^*(s,a)$，选择$Q$值最大的动作就是最优动作。

当环境模型（$P$和$R$）已知时，可以使用动态规划方法求解最优策略。策略迭代包含两个交替进行的步骤：

策略评估（Policy Evaluation）：给定策略$\pi$，计算其价值函数$V^{\pi}$。使用贝尔曼期望方程进行迭代更新：

$$V_{k+1}(s) = \sum_a \pi(a|s) \sum_{s',r} P(s',r|s,a)[r + \gamma V_k(s')]$$

重复迭代直到$V_k$收敛到$V^{\pi}$。

策略改进（Policy Improvement）：根据当前价值函数改进策略。对于每个状态，选择使$Q(s,a)$最大的动作：

$$\pi'(s) = \arg\max_a \sum_{s',r} P(s',r|s,a)[r + \gamma V^{\pi}(s')]$$

策略改进定理保证新策略不会比旧策略差：$V^{\pi'}(s) \geq V^{\pi}(s)$对所有$s$成立。

策略迭代交替进行策略评估和策略改进，直到策略不再改变，此时达到最优策略。

价值迭代直接优化价值函数，省略了显式的策略表示。它使用贝尔曼最优方程进行更新：

$$V_{k+1}(s) = \max_a \sum_{s',r} P(s',r|s,a)[r + \gamma V_k(s')]$$

价值迭代每次迭代都执行一次“贪婪”更新，直接朝着最优价值函数收敛。当价值函数收敛后，通过一次策略提取获得最优策略：

$$\pi(s) = \arg\max_a \sum_{s',r} P(s',r|s,a)[r + \gamma V^*(s')]$$

价值迭代通常比策略迭代收敛更快，因为每次迭代不需要等到价值函数完全收敛。

动态规划方法的主要局限性：

1. 需要环境模型：必须知道状态转移概率$P$和奖励函数$R$，这在许多实际问题中难以获得。

2. 计算复杂度高：每次迭代需要遍历所有状态，对于大规模状态空间（如围棋）不可行。

3. 无法处理连续状态空间：需要离散化，面临维度灾难。

这些局限性推动了无模型（Model-Free）强化学习方法的发展。

蒙特卡洛（Monte Carlo，MC）方法通过采样完整的回合（episode）来估计价值函数，不需要环境模型。

首次访问MC（First-Visit MC）：对于每个状态-动作对$(s,a)$，只在第一次访问$(s,a)$时记录该回合的回报$G$。多次采样后，取平均作为$Q(s,a)$的估计：

$$Q(s,a) = \frac{\sum_{i=1}^{N} G_i}{N}$$

每次访问MC（Every-Visit MC）：每次访问$(s,a)$都记录回报。

MC方法使用大数定律保证：当采样次数趋于无穷时，平均值收敛于期望值。MC的无偏性使其成为可靠的估计方法，但需要完整回合才能更新，不适用于连续任务。

基于MC的控制：使用$\epsilon$-贪婪策略平衡探索与利用。以$1-\epsilon$概率选择当前最优动作，以$\epsilon$概率随机选择动作。随着学习进行，逐渐减小$\epsilon$。

时序差分（Temporal Difference，TD）学习结合了动态规划和蒙特卡洛的优点，可以在不完整回合中更新估计。

TD(0)是最基本的TD算法，更新规则为：

$$V(S_t) \leftarrow V(S_t) + \alpha [R_{t+1} + \gamma V(S_{t+1}) - V(S_t)]$$

其中$\alpha$是学习率，$R_{t+1} + \gamma V(S_{t+1})$是目标值，$\delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t)$是TD误差。

TD用当前估计$V(S_{t+1})$替代真实回报，实现了自举（Bootstrapping）。与MC相比，TD可以在线学习，每步都可以更新，且对初始值敏感。

SARSA（State-Action-Reward-State-Action）是on-policy TD控制算法：

$$Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha [R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t)]$$

SARSA使用实际采取的下一个动作$A_{t+1}$来更新，遵循的是“实际执行的策略”。

Q-Learning是off-policy TD控制算法：

$$Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha [R_{t+1} + \gamma \max_a Q(S_{t+1}, a) - Q(S_t, A_t)]$$

Q-Learning使用最大化操作，学习的是最优动作价值函数，与生成经验的策略无关。Q-Learning收敛到$Q^*$的条件是：所有状态-动作对被无限次访问，且学习率满足Robbins-Monro条件。

TD(0)只考虑一步奖励，MC考虑完整回合回报。多步方法在这之间进行权衡。

n步TD目标值：

$$G_t^{(n)} = R_{t+1} + \gamma R_{t+2} + ... + \gamma^{n-1} R_{t+n} + \gamma^n V(S_{t+n})$$

更新规则：$V(S_t) \leftarrow V(S_t) + \alpha [G_t^{(n)} - V(S_t)]$

TD($\lambda$)通过对不同步数的回报进行加权平均，权重按指数衰减：

$$G_t^{\lambda} = (1-\lambda) \sum_{n=1}^{\infty} \lambda^{n-1} G_t^{(n)}$$

等价实现使用资格迹（Eligibility Traces）：

$$E_t(s) = \gamma \lambda E_{t-1}(s) + \mathbf{1}(S_t=s)$$

$$V(s) \leftarrow V(s) + \alpha \delta_t E_t(s)$$

资格迹记录了每个状态对当前TD误差的贡献程度，实现了高效的信用分配。

当状态空间很大或连续时，无法为每个状态存储单独的价值。值函数逼近使用参数化函数（如神经网络）$\hat{V}(s, \mathbf{w})$或$\hat{Q}(s,a, \mathbf{w})$来近似价值函数。

目标是找到参数$\mathbf{w}$最小化均方误差：

$$J(\mathbf{w}) = \mathbb{E}_{\pi}[(V^{\pi}(S) - \hat{V}(S, \mathbf{w}))^2]$$

使用梯度下降更新参数：

$$\mathbf{w} \leftarrow \mathbf{w} + \alpha [V^{\pi}(S) - \hat{V}(S, \mathbf{w})] \nabla_{\mathbf{w}} \hat{V}(S, \mathbf{w})$$

对于TD方法，使用TD目标代替真实价值：

$$\mathbf{w} \leftarrow \mathbf{w} + \alpha [R + \gamma \hat{V}(S', \mathbf{w}) - \hat{V}(S, \mathbf{w})] \nabla_{\mathbf{w}} \hat{V}(S, \mathbf{w})$$

深度Q网络（Deep Q-Network，DQN）将深度学习与Q-Learning结合，在Atari游戏上取得突破。

DQN面临的两个主要问题及解决方案：

1. 数据相关性：相邻样本高度相关，违反神经网络训练的i.i.d.假设。

经验回放（Experience Replay）：将经验$(s, a, r, s')$存储在回放缓冲区中，训练时随机采样小批量数据。这打破样本相关性，提高数据利用效率。

2. 目标值不稳定：目标$R + \gamma \max_a Q(S', a, \mathbf{w})$依赖于正在更新的参数。

目标网络（Target Network）：使用单独的网络$\mathbf{w}^-$计算目标值，定期从主网络复制参数。这使目标值相对稳定。

DQN损失函数：

$$L(\mathbf{w}) = \mathbb{E}_{(s,a,r,s') \sim D}[(r + \gamma \max_{a'} Q(s', a', \mathbf{w}^-) - Q(s, a, \mathbf{w}))^2]$$

DQN架构使用卷积神经网络处理原始像素输入，输出每个动作的Q值。这种端到端的学习方式展示了深度强化学习的强大能力。

策略梯度方法直接参数化策略$\pi(a|s, \boldsymbol{\theta})$，通过梯度上升优化策略参数。

策略梯度定理：

$$\nabla_{\boldsymbol{\theta}} J(\boldsymbol{\theta}) = \mathbb{E}_{\pi}\left[\sum_a Q^{\pi}(s,a) \nabla_{\boldsymbol{\theta}} \pi(a|s, \boldsymbol{\theta})\right] = \mathbb{E}_{\pi}\left[G_t \nabla_{\boldsymbol{\theta}} \log \pi(A_t|S_t, \boldsymbol{\theta})\right]$$

REINFORCE算法（蒙特卡洛策略梯度）：

$$\boldsymbol{\theta} \leftarrow \boldsymbol{\theta} + \alpha G_t \nabla_{\boldsymbol{\theta}} \log \pi(A_t|S_t, \boldsymbol{\theta})$$

REINFORCE使用完整回合的回报$G_t$进行更新，方差较大。

Actor-Critic架构结合了值函数估计和策略梯度：

1. Actor（演员）：策略网络$\pi(a|s, \boldsymbol{\theta})$，决定动作
2. Critic（评论家）：值函数网络$\hat{V}(s, \mathbf{w})$，评估动作

使用TD误差代替累积回报：

$$\boldsymbol{\theta} \leftarrow \boldsymbol{\theta} + \alpha \delta_t \nabla_{\boldsymbol{\theta}} \log \pi(A_t|S_t, \boldsymbol{\theta})$$

其中$\delta_t = R_{t+1} + \gamma \hat{V}(S_{t+1}, \mathbf{w}) - \hat{V}(S_t, \mathbf{w})$

A3C（Asynchronous Advantage Actor-Critic）：使用多个并行worker异步更新全局网络，去除了经验回放，提高了训练效率。

PPO（Proximal Policy Optimization）：解决策略更新步长过大的问题，使用裁剪的目标函数限制策略变化范围：

$$L^{CLIP}(\boldsymbol{\theta}) = \mathbb{E}\left[\min\left(r_t(\boldsymbol{\theta})\hat{A}_t, \text{clip}(r_t(\boldsymbol{\theta}), 1-\epsilon, 1+\epsilon)\hat{A}_t\right)\right]$$

其中$r_t(\boldsymbol{\theta}) = \frac{\pi_{\boldsymbol{\theta}}(a_t|s_t)}{\pi_{\boldsymbol{\theta}_{old}}(a_t|s_t)}$，$\hat{A}_t$是优势函数估计。

DDPG（Deep Deterministic Policy Gradient）：适用于连续动作空间，使用确定性策略$\mu(s)$和Q函数，采用类似DQN的目标网络和经验回放。

SAC（Soft Actor-Critic）：最大熵强化学习框架，在最大化奖励的同时鼓励策略的随机性，提高探索能力和鲁棒性。

例题1：MDP建模

考虑一个网格世界问题：一个3×3的网格，智能体从(0,0)出发，目标是到达(2,2)。每个格子是一个状态。动作有上、下、左、右四种。每次移动获得-1的奖励，撞到边界保持原位仍获得-1，到达目标获得+10并结束。折扣因子$\gamma=0.9$。

问题：

1. 写出该MDP的五元组表示

2. 计算从(0,0)出发的最优路径及其累积奖励

3. 若采用随机策略（四个动作等概率），计算$V(0,0)$

解答：

1. MDP五元组： - $S = \{(i,j) | i,j \in \{0,1,2\}\}$，共9个状态 - $A = \{\text{上}, \text{下}, \text{左}, \text{右}\}$ - $P$是确定性的：$P((i',j')|(i,j),a) = 1$如果移动有效，否则保持原状态 - $R((2,2), a) = +10$（终止），其他$R = -1$ - $\gamma = 0.9$

2. 最优路径：

最优路径是走最短路径，如：右→右→下→下，或下→下→右→右。

路径：(0,0)→(0,1)→(0,2)→(1,2)→(2,2)

累积奖励：$(-1) + (-1) \times 0.9 + (-1) \times 0.9^2 + 10 \times 0.9^3$

$= -1 - 0.9 - 0.81 + 7.29 = 4.58$

3. 随机策略的价值：

设$V(i,j)$为状态$(i,j)$的价值。对于非目标状态，贝尔曼方程为：

$$V(s) = -1 + \gamma \cdot \frac{1}{4}\sum_{s' \in \text{next}(s)} V(s')$$

设$V(2,2)=0$（终止状态）。通过迭代求解方程组（或观察对称性），对于(0,0)：

平均需要较多步才能到达目标。估算$V(0,0) \approx -5$（考虑多次撞墙和绕路）。

例题2：Q-Learning更新

智能体观察以下转移序列（$\gamma=0.9$，$\alpha=0.1$，初始$Q(s,a)=0$）：

1. $S_0=A, A_0=\text{右}, R_1=-1, S_1=B$
2. $S_1=B, A_1=\text{右}, R_2=+10, S_2=C$（终止）

问题：计算两次Q值更新后的$Q(A, \text{右})$和$Q(B, \text{右})$。

解答：

Q-Learning更新公式：$Q(s,a) \leftarrow Q(s,a) + \alpha [r + \gamma \max_{a'} Q(s',a') - Q(s,a)]$

第一步更新：$Q(B, \text{右})$

当前$Q(C, \cdot) = 0$（终止状态）

$$Q(B, \text{右}) = 0 + 0.1 \times [10 + 0.9 \times 0 - 0] = 1.0$$

第二步更新：$Q(A, \text{右})$

$$Q(A, \text{右}) = 0 + 0.1 \times [-1 + 0.9 \times \max_{a'} Q(B, a') - 0]$$

假设$Q(B, \text{右})=1.0$是当前最大Q值：

$$Q(A, \text{右}) = 0.1 \times [-1 + 0.9 \times 1.0] = 0.1 \times (-0.1) = -0.01$$

最终结果：$Q(B, \text{右}) = 1.0$，$Q(A, \text{右}) = -0.01$

例题3：探索与利用

在一个两摇臂老虎机问题中，摇臂A和B的真实期望奖励分别为$\mu_A=0.6$，$\mu_B=0.4$。当前估计为$\hat{\mu}_A=0.7$（基于10次拉动），$\hat{\mu}_B=0.3$（基于5次拉动）。

问题： 1. 使用$\epsilon$-贪婪（$\epsilon=0.1$）策略，选择A的概率是多少？

2. 使用UCB（Upper Confidence Bound）策略，$c=2$，应该选择哪个摇臂？

3. 讨论$\epsilon$-贪婪和UCB的优缺点

解答：

1. $\epsilon$-贪婪： - 以$1-\epsilon=0.9$概率选择当前最优（A，因为$\hat{\mu}_A > \hat{\mu}_B$） - 以$\epsilon=0.1$概率随机选择（A或B各0.05） - 选择A的总概率：$0.9 + 0.05 = 0.95$

2. UCB：

总拉动次数$n = 10 + 5 = 15$

$UCB_A = 0.7 + 2\sqrt{\frac{\ln 15}{10}} = 0.7 + 2\sqrt{0.27} = 0.7 + 1.04 = 1.74$

$UCB_B = 0.3 + 2\sqrt{\frac{\ln 15}{5}} = 0.3 + 2\sqrt{0.54} = 0.3 + 1.47 = 1.77$

选择B（UCB值更高）

3. 优缺点分析：

1. $\epsilon$-贪婪：
   1. 优点：简单易实现，计算开销小
   2. 缺点：探索是盲目的，持续以固定概率探索，不随知识增加而减少；对已充分探索的动作仍可能浪费探索

1. UCB：
2. 优点：探索是有目的的，优先探索不确定性高的动作；随着采样增加，探索自然减少；有理论保证（对数遗憾界）
3. 缺点：需要知道尝试次数；在复杂环境（如MDP）中计算困难

1. 强化学习中，智能体的目标是：

 A) 最大化即时奖励
 B) 最大化累积折扣奖励
 C) 最小化动作次数
 D) 学习环境的动态模型

2. 以下哪个是马尔可夫性质的正确描述？

 A) 未来状态依赖于完整历史
 B) 未来状态只依赖于当前状态和动作
 C) 所有状态具有相同的价值
 D) 奖励与动作无关

3. Q-Learning是：

 A) On-policy算法
 B) Off-policy算法
 C) 模型预测控制算法
 D) 纯探索算法

4. 在DQN中，经验回放的主要作用是：

 A) 增加网络深度
 B) 打破样本相关性，提高数据效率
 C) 减少计算量
 D) 增加探索

5. SARSA与Q-Learning的主要区别是：

 A) SARSA使用神经网络
 B) SARSA是on-policy，Q-Learning是off-policy
 C) SARSA只能用于离散动作
 D) SARSA不需要学习率

1. MDP的五元组是：状态空间S、动作空间A、$\_\_\_\_$、$\_\_\_\_$、折扣因子$\gamma$。

2. 贝尔曼最优方程中，$V^*(s) = \max_a$$\_\_\_\_$。

3. TD学习中，$\delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t)$被称为$\_\_\_\_$。

4. Actor-Critic架构中，Actor负责$\_\_\_\_$，Critic负责$\_\_\_\_$。

5. 折扣因子$\gamma=0$时，智能体只关注$\_\_\_\_$；$\gamma=1$时，智能体关注$\_\_\_\_$。

1. 考虑以下MDP：状态$A, B, C$，其中$C$是终止状态。转移如下：

1. 从$A$：动作1以概率1到$B$，奖励0；动作2以概率1到$C$，奖励+5
2. 从$B$：唯一动作以概率1到$C$，奖励+10

设$\gamma=0.9$，计算最优价值$V^*(A)$和$V^*(B)$。

2. 使用Q-Learning（$\alpha=0.2$，$\gamma=0.9$），当前Q表如下：

| 状态 | 动作1 | 动作2 |

3. 在一个网格世界（4×4）中，从任意位置到目标的曼哈顿距离为$d$，每步奖励为-1，到达目标奖励为+10。设$\gamma=0.9$，写出最优策略下的价值函数表达式。

1. B。强化学习的目标是最大化累积折扣奖励$G_t = \sum \gamma^k r_{t+k+1}$，而非仅最大化即时奖励。

2. B。马尔可夫性质：$P(s_{t+1}|s_t, a_t, \text{历史}) = P(s_{t+1}|s_t, a_t)$，未来只依赖于当前状态和动作。

3. B。Q-Learning使用$\max_a Q(s',a)$更新，学习最优价值函数，与生成经验的策略无关，是off-policy算法。

4. B。经验回放存储历史经验并随机采样，打破相邻样本的时间相关性，同时提高数据利用效率（同一样本可多次使用）。

5. B。SARSA使用实际采取的下一个动作更新（on-policy），Q-Learning使用最大化操作（off-policy）。

1. 状态转移概率P、奖励函数R（或R）

2. $\sum_{s',r} P(s',r|s,a)[r + \gamma V^*(s')]$

3. TD误差（Temporal Difference Error）

4. 选择动作（执行策略）、评估价值（估计回报）

5. 即时奖励、长期累积奖励（或所有未来奖励之和）

1. 解答：

从$B$：唯一选择到$C$，$V^*(B) = 10 + \gamma \cdot 0 = 10$

从$A$有两个选择：

1. 动作1：到$B$，价值为$0 + \gamma V^*(B) = 0.9 \times 10 = 9$
2. 动作2：到$C$，价值为$5 + \gamma \cdot 0 = 5$

因此$V^*(A) = \max(9, 5) = 9$

答案：$V^*(A) = 9$，$V^*(B) = 10$

2. 解答：

Q-Learning更新：$Q(S_1, \text{动作2}) \leftarrow Q(S_1, \text{动作2}) + \alpha [R + \gamma \max_a Q(S_2, a) - Q(S_1, \text{动作2})]$

$\max_a Q(S_2, a) = \max(2.0, 4.0) = 4.0$

新值：$3.0 + 0.2 \times [2 + 0.9 \times 4.0 - 3.0]$

$= 3.0 + 0.2 \times [2 + 3.6 - 3.0]$

$= 3.0 + 0.2 \times 2.6$

$= 3.0 + 0.52 = 3.52$

答案：更新后$Q(S_1, \text{动作2}) = 3.52$

3. 解答：

设$d$为当前位置到目标的曼哈顿距离（最少步数）。

最优策略下，每步向目标移动，实际经过$d$步到达目标。

价值函数为：$V^*(d) = (-1) + (-1)\gamma + (-1)\gamma^2 + ... + (-1)\gamma^{d-1} + 10\gamma^d$

前$d$项是等比数列：$-\frac{1-\gamma^d}{1-\gamma} = -\frac{1-0.9^d}{0.1} = -10(1-0.9^d) = -10 + 10 \times 0.9^d$

加上终止奖励：$V^*(d) = -10 + 10 \times 0.9^d + 10 \times 0.9^d = -10 + 20 \times 0.9^d$

简化：$V^*(d) = 20 \times 0.9^d - 10$

答案：$V^*(d) = 20 \cdot \gamma^d - 10 = 20 \times 0.9^d - 10$