我可以使用哪些解决方案来解决多臂“多强盗”问题？

人工智能 强化学习 政策梯度 马尔可夫决策过程 多臂强盗 组合优化
2021-11-12 07:38:40

问题

我有 66 台老虎机。对于他们每个人，我有 7 种可能的动作/武器可供选择。在每次试验中，我必须为 66 个插槽中的每一个选择 7 个动作中的一个。奖励取决于这些动作的组合，但槽不相等，即为不同槽拉同一条手臂会得到不同的结果。我不关心初始状态或特征向量，因为问题总是从相同的设置开始（它不是上下文的）。我的奖励取决于我如何同时拉动所有 66 个强盗的 7 个手臂中的一个，正如前面所说，每个插槽都有其独特的属性来计算总奖励。基本上，动作空间是一个单热编码的 66x7 矩阵。

我的解决方案

我忽略了一个事实，即我不关心特征向量或状态，我使用带有基本策略梯度算法的深度神经网络来处理这个问题，根据我得到的奖励，我直接增加每个动作的概率。状态根本不会改变，因此 NN 总是接收相同的输入。这个解决方案确实有效地找到了一个近似最优的策略，但是，它的计算量非常大，而且有些东西告诉我我过度解决了这个问题。

但是，我看不出如何将标准解决方案应用于 MAB，例如 epsilon-greedy。我需要不同的“老虎机”之间的同时性，并且，如果我只是将每个可能的排列视为不同的动作，为了用贪婪的方法探索它们，我会得到太多的动作（按1012）。我在文献中没有发现类似于这种多臂多强盗问题的东西，如果曾经考虑过类似的事情，我一无所知 - 也许我想多了，这可以以某种方式简化为正常的 MAB？

1个回答

尽管您可以将问题描述为老虎机问题或 RL，但它还有其他可行的解释。您评论中的关键信息是：

  • 总奖励不是来自 66 台不同机器的所有结果的简单总和。机器之间存在交互。

  • 总奖励是确定性的。

这看起来像是组合优化中的一个问题。您可以使用许多可能的技术。哪些效果最好将取决于不同机器上的选择之间的非线性和依赖性如何影响最终结果。

最佳案例

对于确定性结果，如果机器之间的更改完全隔离，您可以依次搜索每台机器，因为如果您不更改它们的设置，您可以将所有其他 65 个组件视为常量。这将是非常简单的编码和采取7×66=462寻找最佳结果的步骤。

最差的情况

在最坏的情况下，依赖关系是如此强烈和混乱，以至于在更改单个机器的设置和所有这些设置之间基本上没有可预测的区别。伪随机数生成器和安全散列函数具有此属性，许多具有反馈回路的非常简单的物理系统也具有此属性。

在最坏的情况下，会有一个“神奇的设置”，结果最好，只有通过所有杠杆组合的蛮力搜索才能找到它。

为了应用任何更有效的搜索方法，您必须假设对杠杆组合的响应不是那么混乱。

如何搜索？

从您的描述看来，最好的搜索算法可能介于简单的逐机优化和详尽的全局搜索之间。然而，很难说它在那个范围内的位置。

有几种不同的方法可以将其构建为强化学习。例如，您可以使用当前开关组合作为状态，并将 66 个开关更改作为“情节”运行。

我建议遗传算法非常适合此搜索任务，假设至少存在一些仅限本地的效果，这意味着组合两个好的解决方案很可能会产生第三个好的解决方案。遗传算法不需要计算梯度，并且非常适合离散组合。您的基因组可以简单地是 66 个不同的开关位置，以及这些位置的适应度评分您的黑盒得分。

还有许多其他组合搜索算法可用。足以填满一两本书。一个你可以寻找灵感的地方是Clever Algorithms: Nature-Inspired Programming Recipes，它是一个免费的 PDF。

其它你可能感兴趣的问题
上一篇Facenet人脸识别模型中的三步阈值 下一篇使用 CNN 进行特征提取可以得到哪些特征？