machine-learning - Q 值无限增加，在 Q-Learning 中重复相同操作后循环奖励的结果

Question

我正在通过一个简单的应用程序开发一个简单的 Q-Learning 实现，但有一些事情一直让我困惑。

让我们考虑一下Q-Learning的标准制定

Q(S, A) = Q(S, A) + alpha * [R +  MaxQ(S', A') - Q(S, A)]

假设状态 K 有两个可能的操作，均通过 A 授予我们的代理奖励 R 和 R' 和A'。

如果我们遵循几乎完全贪婪的方法(假设我们假设 0.1 epsilon)，我将首先随机选择一个操作，例如 A。下一次，我可能(90％的时间)再次选择A，这将导致 Q(K, A) 不断增长，事实是这样的，即使是偶然的我尝试 A'，因为它的奖励可能与 A 的奖励大小相同，我们将陷入这样一种情况:在剩下的时间里，几乎不可能从我们的第一次猜测中“恢复”学习的内容。

我想这一定不是这样，否则代理基本上不会学习 - 它只是遵循一个简单的秘诀:像第一次一样做所有事情。

我错过了什么吗？我知道我可以调整 alpha 值(通常是随着时间的推移而减小它)，但这绝不会改善我们的情况。

Answer 1

来自this ，我们知道:

The convergence of Q-learning holds using any exploration policy, and only requires that each state action pair (s,a) is executed infinitely often.

epsilon-greedy policy是探索和利用之间的平衡，既保证了收敛性，又保证了良好的性能。但在实际问题中，我们常常需要一些启发式的方法来改变学习速度alpha代表更好的返回。否则，infinite often要求很难满足。

我在下面列出了一个例子。这是一个经典问题，其中您有一个网格，并且每个单元格中可能有不同的奖励金额。例如，如下所示的 4x4 网格，其中每个单元格都包含 1 的奖励，除了左上角的单元格(您将获得更大的奖励，金额为 10 )。一个机器人正在网格中移动。法律行动正在动LEFT , RIGHT , UP和DOWN ，但机器人无法移出网格。

所以我们的状态空间包含 16 个不同的状态，对应于 16 个单元。由于边界限制，每个州的法律诉讼数量不同。我们的目标是计算最优策略(给定任何状态 s ，输出最优操作 a )。

+++++++++++++++++++++
+ 10 +  1 +  1 + 1  +
+++++++++++++++++++++
+ 1  +  1 +  1 + 1  +
+++++++++++++++++++++
+ 1  +  1 +  1 + 1  +
+++++++++++++++++++++
+ 1  +  1 +  1 + 1  +
+++++++++++++++++++++

假设我们使用 epsilon-greedy policy与 epsilon=0.1 ，恒定的学习率alpha=0.1 。我们从网格上的随机位置开始。每当我们到达左上角时，我们都会再次以随机位置重新开始。

下面是运行 200,000 步模拟的结果。最左边的 block 直观地显示了每个单元格当前的贪婪策略。

• -->向右移动
• <--向左移动
• ^向上移动
• v向下移动

所以你会发现这远非最佳政策。显然，在最优策略中，每个单元格都应该指向左或上，因为我们在位置 (0,0) 处有更大的奖励.

 v   v   v   v   |      2      9      5      4   
 v   v   v   v   |     14     98     75     14   
-->  v   v  <--  |    258   3430   3312    245  
--> --> <-- <--  |   3270  93143  92978   3191  

右侧的 block 显示了到目前为止我们访问每个单元格的次数。您会看到，我们大部分访问都在底部，但很少访问顶行。这就是为什么我们还没有达到最优策略的原因。

如果我们将学习率更改为 alpha=1/(number of times you visited (s,a) so far) ，我们能够在 20,000 步内达到最优策略(如下所示)。此外，我们访问每个单元格的次数分布更加均匀，尽管并不完美。

 --> <-- <-- <--  |     34   7997   7697    294 
  ^   ^   ^  <--  |    731    898    524    132 
  ^   ^   ^   ^   |    709    176     88     94 
  ^   ^   ^   ^   |    245    256     96     77  

对于具有更多状态的更大问题，例如 10x10 网格，我发现最好使用更大的 epsilon 。例如，下面是在 10x10 网格上进行 80,000 次移动后的模拟结果 epsilon=0.5 。除了右下角之外，它几乎是最佳的。还有idea关于使用模拟退火来帮助提高 Q 学习的收敛速度。

 v  <-- <-- <-- <-- <-- <-- <-- <-- <--  |     19   2500   1464    716    386    274    216    159    121     71 
 ^  <-- <-- <-- <--  v  <-- <-- <-- <--  |   9617  11914   3665   1071    580    410    319    225    207    131 
 ^   ^   ^  <-- <-- <-- <--  v  <-- <--  |   5355   5716   2662   1675   1465    611    302    183    162    101 
 ^   ^   ^   ^   ^  <-- <-- <-- <-- <--  |   1604   1887   1192    621   1056    882    693    403    206    100 
 ^   ^   ^   ^   ^   ^   ^  <-- <-- <--  |    639    735    731    333    412    399    480    294    172    114 
 ^   ^   ^  <--  ^   ^   ^  <-- <--  ^   |    373    496    640    454    272    266    415    219    107     98 
 ^   ^   ^   ^   ^   ^   ^   ^  <--  ^   |    251    311    402    428    214    161    343    176    114     99 
 ^   ^   ^   ^  <-- -->  ^  <-- <-- <--  |    186    185    271    420    365    209    359    200    113     70 
 ^   ^   ^   ^   ^   ^   ^   ^   v   v   |    129    204    324    426    434    282    235    131     99     74 
 ^   ^   ^   ^   ^  <--  ^  <-- <-- <--  |    100    356   1020   1233    703    396    301    216    152     78 

顺便说一句，我的玩具问题的 Python 代码(约 100 行)是 here 。