哪种 ML 方法最适合巨大的状态空间?

数据挖掘 机器学习 深度学习 强化学习 无监督学习
2021-10-05 15:45:41

我的问题源于解决看似简单的游戏的挑战。为了节省您完整的规则目录,这里是游戏的简短摘要:

  • 单人纸牌游戏
  • 你通过一副标准的牌,需要为每张牌选择一个动作(不知道下一张牌)
  • 对于每一个选择,你都有很大的可能性(大约 15 叠)来应用卡片 - 给定特定的套装和等级组合,你可以获得积分(很多规则基础 - 因此这个描述代表了游戏的要点设置)

如果牌是已知的,你可以(通过反向传播)计算出完美的选择,以获得最大的分数。直觉上,我尝试编写一个算法来模拟未来尽可能多的动作,以确定最佳选择。即使使用各种剪枝前和剪枝后的方法(例如微不足道的 mini-max),以半可靠的方式计算一个决策也需要数小时(考虑到大多数奖励仅在选择后大约 15 步以上“看到”) .

在过去的几周里,我放弃了这种基本方法,继续寻找可行的强化学习想法。至少可以说,由于各种问题,我感到完全迷失了,即将“卡数”整合到我的状态空间中。我应该包括剩余卡片的完整跟踪(更详细)还是恢复到众所周知的实现(例如 Blackjack 中的 Hi-Lo System.. 与这个项目有很多相似之处)。

总而言之,我想寻求一个有用的建议,以解决自我强化学习的巨大状态空间(“连续”?)问题。我偷看了 DeepQ 学习或类似的东西,但找不到关于像二十一点这样的单人纸牌游戏需要你保持纸牌计数的好的文献。除此之外,延迟的奖励使得与此类项目进行比较变得更加困难。

3个回答

使用带有经验回放的深度 Q 学习网络 (DQN) 使用强化学习 (RL) 对纸牌游戏进行了成功建模。经验回放缓冲区是一个大型元组集合:(状态(s),动作(a),奖励(r),下一个状态(s')。RL代理可以了解哪些组合导致最高奖励。存储表示在可以学习非常大的状态空间表示的深度学习网络中。这种深度学习表示可以代替显式卡片计数。

一种选择是适应 OpenAI 环境。Blackjack已经有一个 OpenAI 环境在您的纸牌游戏在环境中编码后,可以使用 DQN 训练代理。一个很好的起点是Stable Baselines3 (SB3),它是 PyTorch 中强化学习算法的一组可靠实现,作为DQN 实现

我发现多人扑克的 Superhuman AI 是纸牌游戏的好论文。尽管它是在谈论 6 人游戏,但这里仍然有很多用处。例如,他们通过动作抽象将大量的投注动作减少到整数。(但请注意,这主要是为了训练,他们在实际比赛中让它变得灵活。)

这一点听起来也可能适用于您的游戏:

我们在 Pluribus 中使用的另一种抽象形式是信息抽象,其中在显示的信息方面相似的决策点(在扑克中,玩家的牌和显示的棋盘牌)被放在一起并被同等对待

你的描述让我想起的另一个游戏是推箱子,它是单人游戏。您可以认为下一步的移动数只有 4(玩家可以移动的 4 个方向),但从这个角度来看,游戏持续了成百上千的移动,只有当您发现死锁时才会发现移动 N 的错误移动 N+100。(最小化移动次数是评估求解器的常用指标。)

arXiv:1802.04697是一种机器学习方法。我发现这有点令人失望,因为我更想了解当前的最新技术。他们没有将自己的结果与其他推箱子求解器进行比较,我认为这意味着他们的机器学习版本较差,而且最好的求解器仍然是手工制作的专家系统。

但从您的角度来看,这可能使它成为一篇有用的论文,而相关工作应该提供更多的起点。

我从未有过在这样的空间里从事人工智能工作的乐趣。男孩,我会喜欢的。你有很多好东西为你工作

  • 你不需要数据集,因为玩游戏和获胜有效地验证了自己
  • 判断模型的表现相当容易,因为玩游戏并获胜意味着你比你对抗的东西更好(通常)

如果我是你,我会利用这个来为你服务。


对抗性训练策略

就如何训练和测试模型而言,这对我来说似乎是最好的方法。让您的模型与其他模型进行游戏,并根据该游戏的结果进行积极或消极的强化。具体如何选择取决于您自己,但需要考虑一些事项:

  • 你可能想从小游戏开始,这样你的模型就可以“学习基础知识”
  • 您可能想要使用正则化策略,例如批处理游戏、dropout 层等。
  • 在单人游戏中,得分高者获胜。

进化超参数选择

一些人在评论中提到了进化策略。与我特别共鸣的是NEAT,以及它如何处理“物种”中的“繁殖”模型。您可能会对您的问题感兴趣。

您不仅可以使用对抗策略来调整模型权重,还可以根据特定模型函数的适应性来获得胜/败比,从而允许您为特定“物种”模型培育超参数设置。这将允许您同时探索多个建模范例和超参数设置。从本质上讲,这将是随机搜索超参数调整的更智能版本。

型号选择

就选择的实际模型而言,我必须承认这不是我的专业领域。有人提到为用例设计的罐装模型,这可能是不错的选择。一些在我看来似乎可行的建模策略:

(请记住,您可以通过封装在进化策略中让它们相互竞争)

循环神经网络

迭代地拾取卡片并根据该卡片和之前的卡片决定任务,这似乎是 RNN 旨在处理的任务。特别是 LSTM 似乎是一种流行的选择。您可以安装一个 LSTM 作为输入层,并在连续预测之间传递状态,以获得封装长状态空间的有效方法

一个非常大的多维神经网络

您还可以为每张卡片设置一个维度,以及一长串。然后,您可以将其压缩成更小的一系列密集层。这似乎是将您的大空间快速提炼成更抽象、更小的维度空间的好方法。

集成决策树

看起来这些决定很简单,问题是你有很多。您可以使用一组决策树来查看过去卡片历史记录的不同方面,并尝试将它们用作“漏斗”来吐出合理的解决方案。