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

Question

我一直在玩一种算法，学习如何玩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:我认为我既没有学习率，也没有折扣因素。这很重要吗？

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

问题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

Answer 1

因为从零开始就想出了一种实用的tic tic脚趾游戏算法，这是值得称赞的！

问题1:我是否可以成功地证明，我是根据历史来估算奖励，并且仍然声称算法是强化学习，甚至是Q-学习？

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

然而，我认为它被归类为强化学习。您已经实现了RL的以下关键组件：

• 一种状态(当前板)，用作每一步的输入。
• 作为输出的动作(期望的下一板布置)。当该动作有效地直接选择下一个状态时，有时称为后状态表示。它通常用于RL中的确定性游戏。
• 由环境产生的奖励，其中代理人的目标是最大化预期的回报。
• 一种算法，它可以获取关于状态、行为和奖励的数据，并学会通过在环境中获得经验来优化预期的回报。

您的算法最接近于蒙特卡罗控制，这是一个标准的RL方法。

Q学习的最大优点之一是，它将学习一个最优策略，即使在探索--这称为非策略学习--同时，当您的算法是on-策略时，它也会了解它当前行为的价值。这就是为什么你必须降低勘探率随着时间的推移-这可能是一个问题，因为勘探率时间表是一个超参数的学习算法，可能需要仔细调整。

问题2:如果我用神经网络代替基于董事会布局的奖励查找，其中董事会布局是输入，奖励是输出，那么该算法是否可以被看作是深度强化学习？

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

问题3:我认为我既没有学习率，也没有折扣因素。这很重要吗？

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

学习率是一个重要的遗漏。你不能解释你所拥有的东西。您已经放置了update reward for board layout based on game outcome --这个更新步骤通常有它的学习速度。然而，对于和，您实际上可以将学习速率设置为1.0，我猜这与您的方法是一样的，而且它是有效的。我编写的示例代码正是这样做的 -见这一行将学习率设置为1.0。然而，更复杂的场景，特别是在非确定性环境中，会以如此高的学习率学习。

问题4: tictactoe算法可以被归类为真正的学习而不是简单的蛮力吗？

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

我想说的是，在游戏中从当前位置进行的一次彻底的树搜索是“蛮力”。在一个简单的游戏，如tictactoe，这可能比RL更有效率。然而，随着游戏越来越复杂，机器学习方法与搜索的竞争越来越激烈。通常，RL和某种形式的搜索一起使用。