Q值的无限增加,是在Q-Learning中重复相同操作后重复奖励的结果

Question

我正在开发一个简单的Q-Learning实现而不是一个简单的应用程序,但有些东西让我感到困惑.

让我们考虑Q-Learning的标准表述

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

让我们假设这个状态K有两种可能的行为,既可以奖励我们的代理奖励R也可以R'通过A和A'.

如果我们遵循几乎完全贪婪的方法(假设我们假设0.1 epsilon),我将首先随机选择其中一个动作A.下一次,我可能(90%的时间)再次选择A,这将导致Q(K,A)不断增长和增长,即使偶然我尝试A',也可能是它的奖励是真实的情况在与A的相同程度上,我们将进入这样一种情况:在其余学习过程中,几乎不可能从我们的第一次猜测中"恢复".

我想这肯定不是这样,否则代理人基本上不会学习 - 它只是遵循一个简单的方法:像你第一次做的那样做.

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

Answer 1

从这个,我们知道:

Q学习的融合使用任何探索策略,并且仅要求每个状态动作对经常无限地(s,a)执行.

这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 policywith epsilon=0.1,一个恒定的学习率alpha=0.1.我们从网格上的随机位置开始.每当我们到达左上角时,我们会再次以随机位置重新启动.

以下是运行200,000次移动模拟的结果.最左边的块在视觉上显示每个单元格的当前贪婪策略.

• --> 向右移动
• <-- 向左移动
• ^ 向上
• 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  

右侧块显示我们到目前为止访问每个单元的次数.您看到我们将大部分访问时间都放在了最底层,但我们访问的排名非常罕见.这就是我们尚未达到最优政策的原因.

如果我们改变学习率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.除了右下角之外,它几乎是最佳的.还有使用模拟退火来提高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行)就在这里.

Answer 2

Q(K, A)由于这个minus Q(S, A)术语,它不仅会无限增长.如果您将更新规则重写为以下内容,则会更加明显:

Q(S, A) <-- Q(S, A)(1 - a) + a(R + maxQ(S', A'))

这表明它Q(K, A)慢慢走向它的"实际"价值R + maxQ(S', A'). Q(K, A)只会增长到接近那个; 不是无限的.当它停止增长(已接近其实际值)时,Q(K, A)其他的As可以赶上.

无论如何,epsilon的全部意义在于控制你是否希望学习过程更加贪婪(启发式)或探索式(随机),所以如果学习过程太窄,就要增加它.

还要注意QL收敛的一个正式条件是每对(S, A)被访问的次数是无限次的(转述)!所以是的,在培训过程结束时,您希望每一对都被访问了相当多的时间.

祝好运!