これから、次のことがわかります。
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下に移動
ご覧のとおり、これは最適なポリシーとはほど遠いものです。明らかに最適なポリシーでは、すべてのセルが left または up のいずれかを指す必要があります(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 行) はhereです。