Project 3: Reinforcement Learning

Due: 2025.11.03.

---

---

简介

在这个项目中,我们将实现值迭代(Value Iteration)和Q学习(Q-learning)。我们将首先在Gridworld中测试你的智能体,然后将它们应用到吃豆人的具体游戏中。

本次作业所需的文件为：Lab3.zip

你需要编辑的文件

文件	作用
valueIterationAgents.py	一个用于解决基于价值迭代的有模型学习(MDP模型)。
qlearningAgents.py	用于 Gridworld、和Pacman 的Q-learning 智能体。

你可能需要阅读的文件

文件	作用
mdp.py	定义了通用MDP的方法。
learningAgents.py	定义了你的智能体需要继承的基类 ValueEstimationAgent 和 QLearningAgent。
util.py	包含一些实用工具,特别是 util.Counter,对Q-learning 很有帮助。
gridworld.py	Gridworld 的实现代码。
featureExtractors.py	用于为(状态,动作)对提取特征的类。供近似Q-learning 智能体使用。

题目1: 有模型学习-价值迭代方法

在开始这一小节之前,我们先来了解一下将要面对的简单环境 Gridworld。这是一个经典的强化学习环境,你可以把它想象成一个简单的棋盘或迷宫。在这个由方格组成的世界里,有一个用蓝点表示的智能体。

它的任务是在格子之间移动,目标是找到通往“出口”(能获得奖励的地方)的最佳路径,同时可能需要避开“悬崖”(会受到惩罚的陷阱)。

我们将首先尝试采用价值迭代的方法让智能体找到出口。首先,以手动控制模式运行 Gridworld,你可以使用方向键进行操作:

python gridworld.py -m

注意,我们为智能体的移动添加了默认的噪声值0.2。当你按下键盘的“上”键时,智能体只有80%的概率会真正向北移动。剩下分别有10%的概率向西或向东移动。(注意,它有0%的概率朝完全相反的方向移动)

你可以通过运行以下命令查看所有可用的智能体模拟选项。

python gridworld.py -h

下面回顾一下我们在价值迭代:公主营救这一小节ppt中讲到的价值迭代的状态更新方程:

$V(s)=max_{a}\sum_{s^{\prime}\in S}P_{sa}(s^{\prime})(r_{sa}(s^{\prime})+yV^{\pi}(s^{\prime}))$

我们将该方法在我们的GridWorld中实现。请按如下步骤在 valueIterationAgents.py 文件中编写一个价值迭代智能体 ValueIterationAgent:

注意: self.values = util.Counter()我们将所有value值存储于该数据结构。

• computeQValueFromValues (state, action):根据 self.values 给出的价值函数返回 (state, action)对的Q值

  提示:查看 self.mdp.getTransitionStatesAndProbs 的具体实现,并在Q值计算中使用它。

  def computeQValueFromValues (self, state, action):
      """
      Compute the Q-value of action in state from the
      value function stored in self.values.
      """
      "*** YOUR CODE HERE ***"

• runvalueIteration 函数用以实现价值迭代。

  def runvalueIteration (self):
      for i in np.arange(0, self.iterations):
          next_values = util.Counter()
          for state in self.mdp.getStates():
              "*** YOUR CODE HERE ***"
      self.values = next_values

• computeActionFromValues (state):根据 self.values 给出的价值函数计算最佳动作。

  提示:你需要借助 self.mdp.getPossibleActions 函数获取所有可能的动作。

  def computeActionFromValues (self, state):
      """
      The policy is the best action in the given state
      according to the values currently stored in self.values.
  
      You may break ties any way you see fit. Note that if
      there are no legal actions, which is the case at the
      terminal state, you should return None.
      """
      "*** YOUR CODE HERE ***"

请注意: 这里的价值迭代智能体并不是一个强化学习智能体。因此,运行时设定的参数实质是在其初始规划阶段应运行的价值迭代次数(-i 选项指定)。ValueIterationAgent 在构造时会接收一个 MDP模型,并运行指定次数的迭代。

当你实现好后,运行下面的命令验证你的实现。当GridWorld窗口出现后,按任意键即可看到迭代两步后Value值。

python gridworld.py -a value -i 2

请在你的实验报告中给出下列问题的简要推导与计算:

迭代2次后,如何算得(2,2)方格向东的action的Q-Value值是多少?

如果你的代码实现与理论推导均正确，实验观测结果应当与你的计算结果一致。

请注意: 在价值计算中，我们约定：左下角的方格为坐标原点(0,0), 向东(向右)和向北(向上)分别为x轴正方向和y轴正方向。折扣因子是 0.9。绿色出口（坐标(3,2)）奖励为+1，红色陷阱（坐标(3,1)）奖励为-1。所有其他状态的“生存奖励”为0。智能体每一次移动时，有80%的概率朝预定方向移动，有0%的概率朝与预定方向相反的反向移动，分别有10%的概率朝另外两个方向移动。若移动方向为墙体，则反弹回原来位置。

以下命令会迭代计算100次,并尝试测试10次智能体。现在你应该观察到智能体均可以到达出口。

python gridworld.py -a value -i 100 -k 10

---

题目2：策略选择

我们考虑 DiscountGrid 的GridWorld地图: 这个网格有两个带有正收益的终止状态(中间行):一个收益为+1的近处出口和一个收益为+10的远处出口。网格的底行是由带有负收益的终止状态组成的“悬崖”区域;每个状态的收益为-10。起始状态是黄色的方块。

在这个问题中,你需要为MDP选择折扣率(discount)、噪声 (noise)和生存奖励(living reward)的参数设置,以产生几种不同类型的最优策略。你需要尝试生成的策略类型如下:

1. 偏好近处出口(+1),冒险走悬崖(-10)
2. 偏好近处出口(+1),但避开悬崖(-10)
3. 偏好远处出口(+10),冒险走悬崖(-10)
4. 偏好远处出口(+10),但避开悬崖(-10)
5. 避开所有出口和悬崖(即回合永远不结束)

在 analysis.py 文件中, question2a() 到 question2e()每个函数都应该返回一个包含三个元素的元组(discount, noise, living reward)。

请在你的实验报告中简单阐明你是如何针对不同策略类型设计不同参数的。

要查看一组参数最终产生的行为,可以运行以下命令:

python gridworld.py -g DiscountGrid -a value --discount [你的折扣率] --noise [你的噪声] --livingReward [你的生存奖励]

你可以使用自动化评分器验证你的答案:

python autograder.py -q q2

---

题目3： 免模型学习:Q-Learning方法

回顾课堂上提到的有模型学习和无模型学习。

在前面的问题中,我们实现了价值迭代。这是一种典型的“有模型”(model-based)的学习方法。事实上,在整个过程中,我们的价值迭代智能体实际上并不从环境中获得的反馈学习。相反,它通过思考其MDP 模型来得出一个完整的策略,然后才与真实环境互动。

而Q-Learning的思路与 Value Iteration 有一些类似,但它是一种模型无关的(model-free)算法,使用Q-Learning 的时候我们的 agent 无需事先知道当前环境中的State, Action 等 MDP 四元组内容。

在使用 Value Iteration 的时候,我们需要在每一个 episode 对所有的State 和Action 进行更新,但在实际问题中 State 的数量可能非常多以致于我们不可能遍历完所有的状态,这时候我们可以借助Q-Learning,在对于环境未知的前提下,不断地与环境进行交互和探索,计算出有限的环境样本中Q-Value,并维护一个Q-Table:

在刚开始时,agent 对于环境一无所知,因此Q-Table 应该被初始化为一个零矩阵。也即 self.Q_value = util.Counter()

现在你将编写一个Q-learning 智能体。这个智能体在构建时无需构建复杂的MDP模型,而是通过与环境的互动,在 update 方法中与环境不断交互试错学习。qlearningAgents.py 中已经为你提供了一个QLearningAgent的框架。你需要按如下步骤逐步实现函数:

• getQvalue:从Q-Table中直接取出Q值。重要提示:确保在你后续函数中,你只通过调用 getQValue 来访问Q值。

  def getQValue(self, state, action):
      """
      Returns Q(state, action)
      Should return 0.0 if we have never seen a state
      or the Q node value otherwise
      """
      "*** YOUR CODE HERE ***"

• computeValueFromQValues:计算当前状态的Value值。提示:你需要借助 getLegalActions 函数获取所有可能的action,并注意当action为空时的处理。

  def computeValueFromQValues (self, state):
      """
      Returns max_action Q(state, action)
      where the max is over legal actions. Note that if
      there are no legal actions, which is the case at the
      terminal state, you should return a value of 0.0.
      """
      "*** YOUR CODE HERE ***"

• computeActionFromQValues:获取当前状态的Action。提示: 当action为空时,注意返还None。为了获得更好的效果,当有多个action的Q值均为最佳时,你应该在其中随机选取一个。你或许可以使用 random.choice()函数。

  def computeActionFromQValues (self, state):
      """
      Compute the best action to take in a state. Note that if there
      are no legal actions, which is the case at the terminal state,
      you should return None.
      """
      "*** YOUR CODE HERE ***"

• update: 最后,我们应当根据实时的交互和反馈,更新Q值表相关参数。我们按照Q-Learning的更新公式更新Q值表:

  $Q(s, a) \leftarrow Q(s, a) + \alpha(r_{sa}(s^{\prime}) + \gamma \max_{a'} Q(s', a') - Q(s, a))$

  def update (self, state, action, nextState, reward: float):
      """
      The parent class calls this to observe a
      state => action => nextState and reward transition.
      You should do your Q-Value update here
  
      NOTE: You should never call this function,
      it will be called on your behalf.
      """
      "*** YOUR CODE HERE ***"

是时候回到我们的吃豆人了! 运行下面的指令,吃豆人将训练2000次以学习位置和动作的价值,在最后10次利用其学到的策略进行可视化演示:

python pacman.py -p PacmanQAgent -x 2000 -n 2010 -l smallGrid

如果你的方法正确,你应当观察到至少8/10次的获胜情况。

---

题目4（附加题）： 深度强化学习-DQN

本题不额外占分，仅供有兴趣地同学探索。如果你成功解决，我们鼓励你在实验报告中体现。

当环境状态非常复杂或维度过高时,传统的Q-Learning方法因其依赖于庞大的Q-Table而面临巨大的内存挑战。此时我们可以利用神经网络来拟合整个Q-Table,即深度强化学习(DQN)。

具体来说,你需要在 model.py 中实现 DeepQNetwork,这是一个神经网络,用于预测给定状态下所有可能动作的Q值。

你需要实现如下函数:

• __init__: 在这里初始化神经网络的所有参数。你还必须初始化以下变量:

  • self.parameters: 一个包含你所有参数的列表,按前向传播的顺序排列(仅限原始版本项目)。
  • self.learning_rate: 用于 gradient_update()。
  • self.numTrainingGames: 吃豆人用来收集转换数据并学习Q值的游戏次数;注意这个值应该大于1000。
  • self.batch_size: 模型每次梯度更新应使用的转换数据数量。
• get_loss(): 返回预测的Q值(你的网络输出)和Q_targets (你将视为真实值)之间的平方损失。
• run() / forward(): 返回Q网络前向传播的结果。(输出应该是一个大小为(batch_size, num_actions)的向量)。
• gradient_update(): 遍历 self.parameters 并根据计算出的梯度更新每个参数。此函数只应为每个参数执行单次梯度更新。(我们建议使用 Adam 优化器更新梯度)。

运行下面的指令,训练你设计的神经网络,并在最后进行10次可视化测试。

python autograder.py -q q7

如果你的方法正确,你应当观察到至少8/10次的获胜情况。

---

代码提交与评分

请你打包提交valueIterationAgents.py、analysis.py和qlearningAgents.py代码文件(对于完成探索题的同学，可以额外提交model.py),并提交一份pdf或markdown格式的报告。最终提交的压缩包需要命名为"学号_姓名.zip"。请严格按照如下参考文件格式提交。如因格式不合规导致无法评阅或漏评后果自负。

                    学号_姓名.zip
                    │
                    ├── valueIterationAgents.py
                    ├── analysis.py
                    ├── qlearningAgents.py
                    ├── 报告.pdf / 报告.md
                    └── model.py (可选)
                    

你可以多次提交，但请确保提交的文件名与之前的一致。我们会以最后一次提交的文件为准进行评阅。

请注意，不要修改代码文件内其它无关的部分，否则可能无法正常获得本次项目的分数。

第三次实践作业上传链接NJU_box_Project3

学术诚信

我们会将你的代码与课堂上其他提交的代码进行逻辑查重。如果你拷贝了别人的代码,并做一些微小的修改,我们会很容易发现,请不要尝试。我们相信你们会独立完成作业。

致谢

本次项目相关代码基于UC Berkeley CS188课程改写。所有使用及改写均遵循相关协议。感谢他们为社区做出的贡献。