这是一个 Q 学习算法还是只是蛮力？

数据挖掘 机器学习 神经网络 强化学习 q学习
2021-09-21 08:35:46

我一直在玩一种学习如何玩tictactoe的算法。基本伪代码是：

repeat many thousand times {
  repeat until game is over {
    if(board layout is unknown or exploring) {
      move randomly
    } else {
      move in location which historically gives highest reward
    }
  }

  for each step in the game {
    determine board layout for current step
    if(board layout is unknown) {
      add board layout to memory
    }
    update reward for board layout based on game outcome
  }
}

now play a human and win :-)

探索：算法一开始是积极探索的，这会线性减少。在说一千场比赛之后，它只探索了 10% 的动作。所有其他动作都是基于对先前奖励的利用。

奖励：如果游戏获胜，则奖励 10 分。如果比赛结果为平局，则为 0 分，否则为 -5 分。实际上，这些奖励是可以“调整”的，如果游戏时间较短并且获胜，则奖励更多积分，或者如果游戏较长则奖励较少积分。这样，算法更喜欢快速获胜。这意味着它学会了尽快取胜，而不是以后再取胜。这很重要，这样它就不会立即错过胜利——如果它错过了这样的一步，对手可能会 a) 移动到那里以避免让 AI 下次获胜，并且 b) 认为算法很愚蠢，因为它错过了一个“明显的“ 赢。

该算法确实可以学习，因此我可以将其归类为机加工学习算法。

我认为，但我不确定，这是一种强化学习算法。但是，根据https://www.cse.unsw.edu.au/~cs9417ml/RL1/tdlearning.html这不是时间差异学习，因为它直到最后才估计奖励，应该是估计随之而来的奖励。这可能意味着它不是强化学习。

问题 1：我能否成功地辩称我是根据历史估算奖励，并且仍然声称该算法是强化学习甚至 Q 学习？

问题 2：如果我将基于棋盘布局的奖励查找替换为以棋盘布局为输入、奖励为输出的神经网络，该算法是否可以视为深度强化学习？

问题 3：我不认为我有学习率或折扣因子。那很重要吗？

我注意到该算法非常无用，除非我至少用对手尝试的每一个动作来训练它。所以在某种程度上，感觉就像是在使用蛮力，而不是真正的“学习”。这让我质疑机器学习 tictactoe 是否真的在学习。我同意使用神经网络学习图像识别可以归类为学习，因为当它看到未知图像时，它能够说明其分类。但这对于像 tictactoe 这样看起来相似的棋盘布局完全不相关的游戏来说毫无用处（一个可能会导致胜利，另一个可能会导致失败）。所以...

问题 4：tictactoe 算法能否被归类为真正的学习而不是简单的蛮力？

更新：关于奖励......当算法决定去哪里时，它计算出每个位置的奖励如下：

var total = winRewards + drawRewards + lossRewards;
move.reward = (100*(winRewards/total)) + (10*(drawRewards/total)) + (-1*(lossRewards/total));

我除以总点数（每次移动），因为否则它似乎知道一个地方很棒并且不给其他地方机会。通过这种方式，无论播放频率如何，我们都能计算出胜率。与其他人相比，它是标准化的。

代码可在此处获得：https ://github.com/maxant/tictactoe/blob/master/ai.js

更新#2：我后来发现这个算法不能被归类为使用蛮力，因为它在成为专家之前实际上并没有学习那么多游戏。详情在这里：http ://blog.maxant.co.uk/pebble/2018/04/11/1523468336936.html

2个回答

关于定义的问题总是很有趣，所以让我在这里尝试提供另一个答案。

首先，让我们对您正在做的事情进行数学建模。在最高级别，您正在估算某种“奖励”R(s) 对于每个董事会状态 s. 您通过与环境交互并更新您的内部参数（即表R值）以加强有利的行为。因此，根据大多数标准定义，您的算法确实应该归类为强化学习。

要了解你正在做什么样的强化学习以及它是否“好”，我们应该更深入一点。强化学习的关键概念之一是价值函数 五（或它的另一个自我，问函数），它报告了如果您在给定的棋盘状态下进行最佳游戏，您可能期望获得的最佳总奖励。如果你能证明你的算法至少在某种意义上是在估计五，您可以要求一定的“好”保证，并继续将其分类为任何已知的“好”算法类型（它们本质上要么旨在估计五直接，或表现得好像他们隐含地估计了它）。

请注意，当我们谈论两人游戏时，不一定存在唯一的五瞄准。例如，假设获胜奖励 1，失败奖励 0，平局奖励 0.5，不打折，五(空板)是0.5如果您正在与最佳对手比赛，但可能接近1如果你的对手是随机的。如果你和人类比赛，你的五可能因人而异。每个人都知道第一次进入中路是最安全的，但是我自己从来没有用过这样的步法获胜——比赛总是以平局告终。我确实赢了几次，首先移动到角落，因为这让一些对手感到困惑，他们在第一轮就犯了错误。除此之外，假设五 表示与最优对手的博弈是一个合理的选择。

回到你的算法，关键的一步是更新 R，您没有真正指定。让我假设您只是在那里累积分数。如果是这样，我们可以说，严格来说，你不是在做 Q-learning，因为那不是问函数在经典定义中更新。这仍然不意味着您没有隐含地估计正确的五，但是，很难证明或反驳你最终是否这样做。

为了清楚起见，让我稍微调整一下您的算法。而不是将最终奖励加起来R(s) 对于每个州 s，这发生在游戏中，让我们跟踪每个状态所达到的平均奖励。显然，你总是赢的位置，虽然很少达到，但应该比你很少赢的位置更有价值，即使你经常达到，所以我们可能不会因为这个变化而破坏算法，以及整体精神无论如何，学习保持不变。这次改动之后，R(s)变得容易解释 - 这是从位置可以达到的平均预期奖励s.

这个平均预期回报并不是真正的价值函数五我们有兴趣估计。我们的目标五毕竟，应该告诉我们每个职位的最佳预期奖励。然而，有趣的是，当你的策略已经是最优时，你的平均奖励等于你的最优奖励（因为无论如何你总是做最优动作），因此即使你在你的学习中学习了错误的度量，也可能是这样的情况。算法，如果学习过程稍微推动你的算法朝着最佳发挥，随着你逐渐改进你的策略，“平均预期奖励”指标本身慢慢变得“更正确”，最终你开始收敛到正确的价值函数。这纯粹是挥手，但它应该说明很难证明或反驳你的算法是否正式学习它应该学习的东西。也许确实如此。

无论如何，让我们不要跟踪每个状态的平均奖励，而是更改您的算法以跟踪迄今为止的最佳奖励。这意味着，您将检查每个位置的所有替代移动，并且只更新R(s)如果您当前的举动导致未来得分有所提高（与您可以从该州采取的替代选择相比）。恭喜，现在您的算法等效于通常的 Q-learning 方法（更准确地说是“值迭代”方法）。

最后，“是学习还是蛮力”是一个有效的问题。“学习”这个词至少可以用两种不同的方式来解释。首先，学习可能意味着简单的记忆。例如，如果我发现第一次移到中心是好的，我可以把这个事实写在一个表格中，以后直接使用这个事实。人们将这种记忆称为“学习”，但这种学习真的很愚蠢。

第二个通常被赋予“学习”的不同含义是泛化。在这种情况下，除了简单地写下哪些动作是好的之外，您的算法还可以将此信息推广到以前看不见的动作。这就是“智能”的学习方式。

Q-learning 以及许多其他 RL 算法通常是根据表的更新来制定的五或者问. 因此，它们本质上是“愚蠢的学习”算法，甚至不旨在概括状态信息。只有当您开始使用具有内置泛化能力的东西（例如神经网络）对状态或策略进行建模时，才会出现真正的泛化（又名“智能学习”） 。

所以，总结一下。是的，您的算法是强化学习。不，这不是 Q-learning，而是稍作改动就变成了 Q-learning。是的，它更像是“蛮力”而不是“智能学习”，但默认的 Q-learning 也是如此。是的，通过使用神经网络对状态进行建模来添加泛化会使算法“更智能”。

感谢您从头开始找出有效的井字游戏算法！

问题 1：我能否成功地辩称我是根据历史估算奖励，并且仍然声称该算法是强化学习甚至 Q 学习？

首先，这绝对不是Q 学习。

但是，我确实认为它归类为强化学习。您已经实现了 RL 的这些关键组件：

  • 一个状态（当前棋盘），用作每一步的输入。

  • 一个动作（期望的下一个棋盘排列），用作输出。当动作是有效地直接选择下一个状态时，这有时称为后状态表示。它通常在 RL 中用于确定性游戏。

  • 环境产生的奖励，其中代理的目标是最大化预期奖励。

  • 一种算法，可以获取有关状态、动作和奖励的数据，并通过在环境中获得经验来学习优化预期奖励。

您的算法最接近 IMO蒙特卡洛控制，这是一种标准的 RL 方法。

Q Learning 的一大优势是即使在探索时它也会学习最优策略——这被称为离策略学习，而你的算法是在策略的，即它了解它当前行为方式的值。这就是为什么您必须随着时间的推移降低探索率 - 这可能是一个问题，因为探索率计划是您的学习算法的超参数，可能需要仔细调整。

问题 2：如果我将基于棋盘布局的奖励查找替换为以棋盘布局为输入、奖励为输出的神经网络，该算法是否可以视为深度强化学习？

是的，我想这将是技术上的。然而，仅仅通过添加神经网络来估计动作值是不可能很好地扩展到更复杂的问题的，除非你添加一些更复杂的元素，例如使用时间差分学习或策略梯度。

问题 3：我不认为我有学习率或折扣因子。那很重要吗？

折扣因子对于偶发问题并不重要。只有连续问题才有必要，在这种情况下，您需要有某种时间范围，否则预测的奖励将是无限的（尽管在实践中您也可以用平均奖励方法替换折扣机制）。

学习率是一个重要的遗漏。你没有解释你有什么代替它。你已经放了update reward for board layout based on game outcome- 该更新步骤通常包含学习率。但是，对于井字游戏和 Q-Learning，您实际上可以将学习率设置为 1.0，我猜这与您的方法相同，并且有效。我已经编写了完全可以做到这一点的示例代码- 请参阅将学习率设置为 1.0 的这一行。然而，更复杂的场景，尤其是在非确定性环境中，会在如此高的学习率下学习得不好。

问题 4：tictactoe 算法能否被归类为真正的学习而不是简单的蛮力？

你的算法肯定是在从经验中学习一些东西，尽管与人类相比效率低下。但是，许多更基本的 RL 算法都有类似的问题，并且通常需要多次查看系统的每个可能状态，然后才能收敛到答案。

我会说在游戏过程中从当前位置进行详尽的树搜索是“蛮力”。在像 tictactoe 这样的简单游戏中，这可能比 RL 更有效。然而，随着游戏变得越来越复杂，机器学习方法与搜索竞争。RL 和某种形式的搜索通常一起使用。

其它你可能感兴趣的问题
上一篇tensorflow中指标列和分类标识列的区别 下一篇您如何评估已在生产中部署的 ML 模型？