Q学習

Q学習は、エージェントが特定の状態にあることを条件として、エージェントが取る可能性のある各アクションに値を割り当てるようにエージェントに教えるモデルフリーの 強化学習アルゴリズムです。環境のモデルを必要とせず (したがって「モデルフリー」)、適応を必要とせずに確率的遷移と報酬の問題を処理できます。 ^[1]

有限マルコフ決定プロセスの場合、Q学習は、現在の状態から始めて、すべての連続ステップにわたって総報酬の期待値を最大化するという意味で最適なポリシーを見つけます。^[2] Q学習は、無限の探索時間と部分的にランダムなポリシーを与えられた任意の有限マルコフ決定プロセスに対して最適なアクション選択ポリシーを識別できます。 ^[2]「Q」は、アルゴリズムが計算する関数、つまり特定の状態で実行されるアクションに対する期待報酬を指します。^[3]

強化学習には、エージェント、一連の状態 、および状態ごとの一連のアクションが含まれます。アクションを実行することで、エージェントは状態から状態へと遷移します。特定の状態でアクションを実行すると、エージェントに報酬(数値スコア) が与えられます。 ${\displaystyle {\mathcal {S}}}$${\displaystyle {\mathcal {A}}}$${\displaystyle a\in {\mathcal {A}}}$

エージェントの目標は、総報酬を最大化することです。これは、将来の状態から得られる最大の報酬を現在の状態を達成するための報酬に追加することで実現され、潜在的な将来の報酬によって現在の行動に効果的に影響を及ぼします。この潜在的な報酬は、現在の状態から始まるすべての将来のステップの報酬の期待値の加重合計です。 ^[1]

例として、電車に乗るプロセスを考えてみましょう。このプロセスでは、報酬は乗車に費やした合計時間のマイナスで測定されます (または、電車に乗るコストは乗車時間に等しい)。1 つの戦略は、電車のドアが開いたらすぐに入り、最初の待ち時間を最小限に抑えることです。ただし、電車が混雑している場合は、ドアに入るという最初のアクションの後、乗車しようとすると、人々が電車から降りようと争うため、ゆっくりと入ることができます。その場合、合計乗車時間、つまりコストは次のようになります。

• 待機時間 0 秒 + 戦闘時間 15 秒

翌日、偶然 (探索) により、他の人が先に出発できるように待つことにしました。これにより、最初は待ち時間が長くなります。ただし、出発する乗客と争う時間は短くなります。全体として、このパスは前日よりも報酬が高く、合計搭乗時間は次のようになります。

• 待機時間 5 秒 + 戦闘時間 0 秒

探索を通じて、最初の（忍耐強い）行動は強制的な戦略よりも大きなコスト（またはマイナスの報酬）をもたらすにもかかわらず、全体的なコストは低くなり、より報酬の高い戦略が明らかになります。

未来にステップを踏んだ後、エージェントは次のステップを決定します。このステップの重みは として計算されます。ここで、(割引係数) は 0 から 1 の間の数値です ( )。 と仮定すると、これは、先に受け取った報酬を後で受け取った報酬よりも高く評価する効果があります (「良いスタート」の価値を反映します)。 は、各ステップで成功 (または生き残る) する確率として解釈することもできます。 ${\displaystyle \Delta t}$${\displaystyle \gamma ^{\Delta t}}$${\displaystyle \gamma }$${\displaystyle 0\leq \gamma \leq 1}$${\displaystyle \gamma <1}$${\displaystyle \gamma }$${\displaystyle \Delta t}$

したがって、このアルゴリズムには、状態とアクションの組み合わせの品質を計算する関数があります。

${\displaystyle Q:{\mathcal {S}}\times {\mathcal {A}}\to \mathbb {R} }$。

学習が始まる前に、⁠ ⁠ は${\displaystyle Q}$（プログラマが選択した）任意の固定値に初期化されます。その後、エージェントがアクションを選択するたびに、報酬を観察し、新しい状態（前の状態と選択されたアクションの両方に依存する可能性があります）に入り、更新されます。アルゴリズムの核となるのは、現在の値と新しい情報の加重平均を使用した単純な値反復更新としてのベルマン方程式です。^[4]${\displaystyle t}$${\displaystyle A_{t}}$${\displaystyle R_{t+1}}$${\displaystyle S_{t+1}}$${\displaystyle S_{t}}$${\displaystyle Q}$

${\displaystyle Q^{new}(S_{t},A_{t})\leftarrow (1-\underbrace {\alpha } _{\text{learning rate}})\cdot \underbrace {Q(S_{t},A_{t})} _{\text{current value}}+\underbrace {\alpha } _{\text{learning rate}}\cdot {\bigg (}\underbrace {\underbrace {R_{t+1}} _{\text{reward}}+\underbrace {\gamma } _{\text{discount factor}}\cdot \underbrace {\max _{a}Q(S_{t+1},a)} _{\text{estimate of optimal future value}}} _{\text{new value (temporal difference target)}}{\bigg )}}$

ここで、は状態 から状態 に移行するときに受け取る報酬であり、 は学習率です。 ${\displaystyle R_{t+1}}$${\displaystyle S_{t}}$${\displaystyle S_{t+1}}$${\displaystyle \alpha }$ ${\displaystyle (0<\alpha \leq 1)}$

3 つの要素の合計である ことに注意してください。${\displaystyle Q^{new}(S_{t},A_{t})}$

• ${\displaystyle (1-\alpha )Q(S_{t},A_{t})}$: 現在の値（学習率を1引いた値で重み付け）
• ${\displaystyle \alpha \,R_{t+1}}$:状態にあるときにアクションをとった場合に得られる報酬（学習率によって重み付けされる）${\displaystyle R_{t+1}}$${\displaystyle A_{t}}$${\displaystyle S_{t}}$
• ${\displaystyle \alpha \gamma \max _{a}Q(S_{t+1},a)}$: 状態から得られる最大報酬（学習率と割引率で重み付け）${\displaystyle S_{t+1}}$

アルゴリズムのエピソードは、状態が最終状態または終端状態になると終了します。ただし、Q学習は非エピソードタスクでも学習できます (収束無限級数の特性による)。割引率が 1 未満の場合、問題に無限ループが含まれる場合でも、アクション値は有限です。 ${\displaystyle S_{t+1}}$

すべての最終状態 について、は更新されることはなく、状態 で観測された報酬値に設定されます。ほとんどの場合、はゼロに等しくなります。 ${\displaystyle s_{f}}$${\displaystyle Q(s_{f},a)}$${\displaystyle r}$${\displaystyle s_{f}}$${\displaystyle Q(s_{f},a)}$

学習率またはステップサイズは、新しく獲得した情報がどの程度古い情報に優先するかを決定します。係数 0 ではエージェントは何も学習しません (事前知識のみを活用します)。一方、係数 1 ではエージェントは最新の情報のみを考慮します (可能性を探索するために事前知識を無視します)。完全に決定論的な環境では、学習率 が最適です。問題が確率的である場合、アルゴリズムは、いくつかの技術的条件下で学習率がゼロに減少することを要求する学習率 に収束します。実際には、すべての に対してなど、一定の学習率が使用されることがよくあります。^[5]${\displaystyle \alpha _{t}=1}$${\displaystyle \alpha _{t}=0.1}$${\displaystyle t}$

割引係数⁠ ⁠${\displaystyle \gamma }$は将来の報酬の重要性を決定します。係数が 0 の場合、エージェントは現在の報酬のみを考慮することで「近視眼的」になります (つまり、上記の更新規則の場合)。一方、係数が 1 に近づくと、長期的に高い報酬を目指すようになります。割引係数が 1 に達するかそれを超えると、アクションの値が発散する可能性があります。⁠ ⁠の場合、終端状態がない場合、またはエージェントが終端状態に到達しない場合は、すべての環境履歴が無限に長くなり、加算的で割引されていない報酬を持つ効用は一般に無限になります。^[6]割引係数が 1 よりわずかに低い場合でも、価値関数が人工ニューラルネットワークで近似されると、 Q関数学習によってエラーと不安定性が伝播します。^[7]その場合、割引係数を低く設定して最終値に向かって増加させると、学習が加速されます。^[8]${\displaystyle r_{t}}$${\displaystyle \gamma =1}$

Q学習は反復アルゴリズムであるため、最初の更新が行われる前に暗黙的に初期条件を仮定します。「楽観的初期条件」とも呼ばれる高い初期値は、探索を促進できます。^つまり、どのアクションが選択されても、更新ルールによって他の選択肢よりも低い値になり、選択確率が高くなります。最初の報酬を使用して初期条件をリセットできます。^[10]このアイデアによると、アクションが最初に実行されるときに、報酬を使用して の値を設定します。これにより、固定された決定論的報酬の場合に即時学習が可能になります。初期条件のリセット(RIC) を組み込んだモデルは、任意の初期条件(AIC)を仮定するモデルよりも参加者の行動をより正確に予測すると期待されます。^[10] RIC は、繰り返しのバイナリ選択実験における人間の行動と一致しているようです。^[10]${\displaystyle r}$${\displaystyle Q}$

Q学習は、最も単純な方法ではデータをテーブルに保存します。エージェントが特定の状態を訪れて特定のアクションを実行する可能性がますます小さくなるため、このアプローチは状態/アクションの数が増えるにつれて機能しなくなります。

Q学習は関数近似と組み合わせることができる。^[11]これにより、状態空間が連続している場合でも、アルゴリズムをより大きな問題に適用することが可能になる。

1つの解決策は、（適応された）人工ニューラルネットワークを関数近似器として使用することです。 ^[12]もう1つの可能性は、ファジールール補間（FRI）を統合し、離散QテーブルまたはANNの代わりにスパースファジールールベース^[13]を使用することです。これは、人間が読める知識表現形式であるという利点があります。関数近似は、アルゴリズムが以前の経験を以前は見たことのない状態に一般化できるため、有限の問題での学習を高速化する可能性があります。

状態/アクション空間を縮小する別の手法は、可能な値を量子化することである。棒を指の上でバランスをとることを学習する例を考えてみよう。ある時点の状態を記述するには、空間における指の位置、速度、棒の角度、棒の角速度が必要となる。これにより、1 つの状態を記述する 4 要素ベクトル、つまり 4 つの値にエンコードされた 1 つの状態のスナップショットが得られる。問題は、可能な状態が無限に存在することである。有効なアクションの可能な空間を縮小するには、複数の値をバケットに割り当てることができる。開始位置からの指の正確な距離 (-Infinity から Infinity) は不明であるが、指が遠いか遠いか (近いか遠いか) は不明である。^[14]

Q学習は1989年にクリス・ワトキンスによって導入されました。^[15]収束証明は1992年にワトキンスとピーター・ダヤンによって発表されました。 ^[16]

ワトキンスは、博士論文のタイトルである「遅延報酬からの学習」に取り組んでいました。8年前の1981年に、同じ問題が「遅延強化学習」という名前で、ボジノフスキーのクロスバーアダプティブアレイ（CAA）によって解決されました。^{[17] [18]}メモリマトリックスは、8年後のQ学習のQテーブルと同じでした。このアーキテクチャにより、強化学習に「状態評価」という用語が導入されました。論文では 数学的な擬似コードで記述されたクロスバー学習アルゴリズムは、各反復で次の計算を実行します。${\displaystyle W=\|w(a,s)\|}$

• 状態sでアクションa を実行します。
• 結果状態s'を受信します。
• 状態評価を計算する⁠ ⁠${\displaystyle v(s')}$ ;
• クロスバー値を更新します。${\displaystyle w'(a,s)=w(a,s)+v(s')}$

「二次強化」という用語は動物学習理論から借用されたもので、バックプロパゲーションを介して状態値をモデル化するために使われます。つまり、結果状況の状態値は、以前${\displaystyle v(s')}$に遭遇した状況にバックプロパゲーションされます。CAA は状態値を垂直に、アクションを水平に計算します (「クロスバー」)。遅延強化学習を示すデモンストレーション グラフには、状態評価関数によって計算された状態 (望ましい状態、望ましくない状態、中立状態) が含まれていました。この学習システムは、Q 学習アルゴリズムの先駆けでした。^[19]

2014年にGoogle DeepMindは、深層学習へのQ学習の応用である「深層強化学習」または「深層Q学習」の特許を取得しました^{[20] 。この技術は、} Atari 2600のゲームを人間の専門家レベルで プレイすることができます。

DeepMindシステムは、受容野の効果を模倣するために、タイル状の畳み込みフィルタの層を備えた深層畳み込みニューラルネットワークを使用しました。ニューラルネットワークなどの非線形関数近似器を使用してQを表現すると、強化学習は不安定または発散します。この不安定性は、観測シーケンスに存在する相関関係、Qへの小さな更新がエージェントのポリシーとデータ分布を大幅に変更する可能性があるという事実、およびQとターゲット値との相関関係に起因します。この方法は、さまざまなドメインとアプリケーションでの確率的検索に使用できます。^{[1] [21]}

この技術は、経験再生という生物学にヒントを得たメカニズムを使用しており、最新の行動ではなく、以前の行動のランダムなサンプルを使用して続行します。^[3]これにより、観測シーケンスの相関が除去され、データ分布の変化が滑らかになります。反復更新により、定期的に更新されるターゲット値に向けてQが調整され、ターゲットとの相関がさらに低下します。^[22]

Q学習における将来の最大近似行動値は、現在の行動選択ポリシーと同じQ関数を使用して評価されるため、ノイズの多い環境ではQ学習が行動値を過大評価し、学習が遅くなることがあります。これを修正するために、Double Q学習と呼ばれる変種が提案されました。Double Q学習^[23]は、オフポリシー強化学習アルゴリズムであり、次の行動を選択するために使用されるものとは異なるポリシーを値の評価に使用します。

実際には、2 つの別個の価値関数が 、別々の経験を使用して相互に対称的な方法でトレーニングされます。二重 Q 学習の更新手順は次のようになります。 ${\displaystyle Q^{A}}$${\displaystyle Q^{B}}$

${\displaystyle Q_{t+1}^{A}(s_{t},a_{t})=Q_{t}^{A}(s_{t},a_{t})+\alpha _{t}(s_{t},a_{t})\left(r_{t}+\gamma Q_{t}^{B}\left(s_{t+1},\mathop {\operatorname {arg~max} } _{a}Q_{t}^{A}(s_{t+1},a)\right)-Q_{t}^{A}(s_{t},a_{t})\right)}$、 そして

${\displaystyle Q_{t+1}^{B}(s_{t},a_{t})=Q_{t}^{B}(s_{t},a_{t})+\alpha _{t}(s_{t},a_{t})\left(r_{t}+\gamma Q_{t}^{A}\left(s_{t+1},\mathop {\operatorname {arg~max} } _{a}Q_{t}^{B}(s_{t+1},a)\right)-Q_{t}^{B}(s_{t},a_{t})\right).}$

現在、割引後の将来の推定値は別のポリシーを使用して評価され、過大評価の問題が解決されています。

このアルゴリズムは2015年に改良され、 DQNアルゴリズムと同様にディープラーニングと組み合わせられ、^[24]、オリジナルのDQNアルゴリズムよりも優れた性能を持つダブルDQNが誕生しました。^[25]

遅延Q学習はオンラインQ学習アルゴリズムの代替実装であり、おそらく近似的に正しい（PAC）学習である。^[26]

貪欲GQは、（線形）関数近似と組み合わせて使用​​するQ学習の一種です。 ^[27]貪欲GQの利点は、関数近似を使用してアクション値を推定する場合でも収束が保証されることです。

分布Q学習はQ学習の変形であり、各行動の期待収益ではなく収益の分布をモデル化しようとするものである。これはディープニューラルネットワークによる推定を容易にし、リスクに敏感な制御などの代替制御方法を可能にすることが観察されている。^[28]

Q学習はマルチエージェント設定で提案されている（^[29]のセクション4.1.2を参照）。1つのアプローチは、環境が受動的であると仮定することです。^[30] LittmanはミニマックスQ学習アルゴリズムを提案しています。^[31]

標準的なQ学習アルゴリズム（テーブルを使用）は、離散的な行動と状態空間にのみ適用されます。これらの値を離散化すると、主に次元の呪いにより、学習効率が低下します。しかし、この問題を解決しようとするQ学習の適応型として、ワイヤーフィットニューラルネットワークQ学習があります。^[32]${\displaystyle Q}$

• 強化学習
• 時間差学習
• サルサ
• 反復囚人のジレンマ
• ゲーム理論

• Watkins, CJCH (1989)。遅延報酬からの学習。博士論文、ケンブリッジ大学、ケンブリッジ、イギリス。
• Strehl, Li, Wiewiora, Langford, Littman (2006). PAC モデルフリー強化学習
• 強化学習: 入門、Richard Sutton と Andrew S. Barto 著、オンライン教科書。「6.5 Q 学習: オフポリシー TD 制御」を参照してください。
• Piqle: 強化学習のための汎用 Java プラットフォーム
• 強化学習迷路、 Q学習を使用してアリを迷路に導くデモンストレーション
• ジェラルド・テサウロによるQ学習の研究