在将问题表述为 MDP 时，您需要定义系统的状态、您可以采取的可能行动、取决于行动的状态之间的转换概率以及状态转换所获得的奖励（或支付的成本）。这里的重要部分是创建一个具有马尔可夫属性的状态空间，简单地说，这意味着在任何给定状态下，您都有足够的信息来做出最佳决策。

• 奖励：在这种情况下，我认为很明显，如果我们找出数字，则应该给予积极的奖励，如果不知道，则应该给予零奖励。

• 动作：我们可以采取的动作是猜测，即可能的动作将来自动作空间A=(1,2,3)。

• 州：这有点难以提出。在这里，直觉应该来自思考你可以采取的行动以及它们如何改变你所拥有的关于系统的信息。在我们的状态空间中，每个状态将代表答案可能是的一组数字。例如，在一个状态下，(1,3)我们知道猜测的数字是1或3。此外，我们将用大写字母表示这些状态以简化状态转换。

  • A=(1, 2, 3)：搜索开始时的初始状态，猜测的数字可以是1、2或3；
  • B=(1, 2)：猜出的数字是1或2；
  • C=(1, 3)：猜出的数字是1或3；
  • D=(2, 3)：猜出的数字是2或3；
  • E=(1)：猜到的数只能是1；
  • F=(2)：猜到的数只能是2；
  • G=(3)：猜出的数字只能是3；
  • H=()：最终状态，我们找到了猜测的数字。

• 状态转换：这很简单，只要根据我们所做的猜测（动作）想象在一个状态下哪些状态是可达的。这里的符号 P(A|B,1) 表示我们从状态 B 到达状态 A 的概率，假设我们猜到了1。（注意：我们将假设猜测数字的均匀分布）。我想我会在这里偷懒，不会写下所有的转换，因为一旦你了解了它们是如何制作的，它们就会变得非常重复，我只会为所有情况提供示例。

  • P(D|A,1)=2/3：我们在初始状态下猜测1并且我们错过了 2/3 的机会，回复将是猜测的数字大于1。
  • P(H|A,1)=1/3：我们猜对了，所以我们到达了最终状态。
  • P(B|A,3)=2/3：类似地，我们猜测3并错过。
  • P(H|A,3)=1/3：我们猜对了3。
  • P(C|A,2)=0：如果我们的猜测2是错误的，我们会得到一个关于猜测的数字是大于还是小于2的回复，因此我们不会进入这种状态。
  • P(E|A,2)=1/3：我们猜测2，答案是数字小于2。
  • P(G|A,2)=1/3
  • P(H|A,2)=1/3
  • P(B|B,3)=1：在状态 B 中猜测3并不能提供更多信息，因此我们以概率 1 到达相同的状态。
  • P(H|B,1)=1/2：1是该状态下 1/2 概率的正确猜测。
  • P(F|B,1)=1/2：同样，如果我们猜测1 ，我们有 1/2 的机会错过，所以我们到达状态 F，我们知道什么是好的解决方案，但是我们还没有获胜，因为我们仍然需要再进行一次猜测以达到最终状态。
  • P(F|F,1)=1：再次在状态 F 中猜测1并没有给我们额外的信息，所以我们回到状态 F。
  • P(H|F,2)=1：但是，在状态 F 中猜测2会给我们最终状态，因为它是正确的猜测。

请注意，我之前定义了 8 个状态，但是，状态 C=(1,3) 从未达到，因此我们实际上并不需要它。

我希望这会有所帮助，您将能够完成其余的工作。