Q-learningは、環境のモデルを必要とせずに、エージェントが現在の状態に基づいて可能な行動に価値を割り当てるように訓練する、モデルフリーの強化学習アルゴリズムである。確率的な遷移と報酬を伴う問題を、適応を必要とせずに扱うことができる。任意の有限マルコフ決定過程に対して、Q-learningは、無限の探索時間と部分的なランダムポリシーを前提とした場合、現在の状態から始まる任意の連続するステップ全体にわたる総報酬の期待値を最大化するという意味で、最適なポリシーを見つける。「Q」は、このアルゴリズムが計算する関数、すなわち、与えられた状態で取られた行動の期待報酬（つまり、その質）を指す。
簡単な例として、グリッド迷路のエージェントが10点の価値がある出口に到達することを学ぶ場合を考える。分岐点では、Q-learningは、右に進む方が左に進むよりも速く出口に到達する場合、右に進むことに高い価値を割り当てるかもしれない。これは、時間をかけて両方向を試すことでこの選択を改善する。この例は、アルゴリズムが即時報酬と長期的な結果のバランスを、反復的な更新を通じてどのように取るかを示している。
強化学習の文脈
強化学習は、エージェント、状態の集合\(\mathcal{S}\)、および各状態における行動の集合\(\mathcal{A}\)を含む。行動\(a \in \mathcal{A}\)を実行することにより、エージェントは状態から状態へ遷移する。特定の状態で行動を実行すると、エージェントには報酬、つまり数値スコアが与えられる。エージェントの目標は、現在の状態を達成するための報酬に、将来の状態から得られる最大報酬を加算することで総報酬を最大化することであり、これにより現在の行動が将来の潜在的な報酬によって効果的に影響を受ける。この潜在的な報酬は、現在の状態から始まるすべての将来のステップの報酬の期待値の加重和である。
例として、電車に乗ることを考え、報酬が総乗車時間の負の値で測定される場合を考える。一つの戦略は、ドアが開いたらすぐに電車のドアに入り、初期の待ち時間を最小化することである。しかし、電車が混雑している場合、降車する乗客が出口に向かって争うため、入場は遅い。この場合の総乗車時間は、0秒の待ち時間プラス15秒の争い時間となる。翌日、偶然（探索）により、エージェントは待って他の人を先に降りさせることで、より長い待ち時間だが争い時間は少なくなる。全体として、この経路は総乗車時間が5秒の待ち時間プラス0秒の争い時間であるため、より高い報酬を持つ。探索を通じて、最初の忍耐強い行動が強引な戦略よりも大きなコストをもたらすにもかかわらず、全体のコストは低く、より報酬の高い戦略が明らかになる。
アルゴリズムの仕組み
\(\Delta t\)ステップ未来に進んだ後、エージェントは次のステップを決定する。このステップの重みは\(\gamma^{\Delta t}\)として計算され、ここで\(\gamma\)（割引率）は0と1の間の数値である。\(\gamma < 1\)を仮定すると、これは後で受け取る報酬よりも早く受け取る報酬を高く評価し、良いスタートの価値を反映する。\(\gamma\)は、各ステップ\(\Delta t\)で成功または生存する確率として解釈することもできる。
このアルゴリズムは、状態と行動の組み合わせの質を計算する関数\(Q: \mathcal{S} \times \mathcal{A} \to \mathbb{R}\)を持つ。学習が始まる前に、\(Q\)はプログラマーによって選ばれた任意の固定値に初期化される。各時間\(t\)で、エージェントは行動\(A_t\)を選択し、報酬\(R_{t+1}\)を観察し、新しい状態\(S_{t+1}\)（これは前の状態\(S_t\)と選択された行動の両方に依存する可能性がある）に入り、\(Q\)が更新される。核心的な更新は、ベルマン方程式を単純な値反復更新として用いたもので、現在の値と新しい情報の加重平均を使用する：
\(Q_{new}(S_t, A_t) \leftarrow (1 - \alpha) \cdot Q(S_t, A_t) + \alpha \cdot [R_{t+1} + \gamma \max_a Q(S_{t+1}, a)]\)
ここで、\(\alpha\)は学習率であり、新しい情報が古い情報をどの程度上書きするかを制御する。
探索と活用
このアルゴリズムは、探索（報酬を発見するために新しい行動を試すこと）と活用（高い報酬をもたらすと知られている行動を選択すること）のバランスに依存している。イプシロン・グリーディのような部分的なランダムポリシーは、ほとんどの場合で最もよく知られた行動を選択するが、時折ランダムな行動を選んで探索する。これにより、エージェントは時間の経過とともに推定を改善でき、電車の乗車例でランダムな探索がより良い戦略を明らかにしたように、学習が可能になる。
収束と最適性
任意の有限マルコフ決定過程に対して、Q-learningは、無限の探索時間と適切な学習率スケジュールを前提とした場合、任意の開始状態から期待総報酬を最大化する最適なポリシーに収束する。このアルゴリズムは、環境の遷移ダイナミクスのモデルを必要とせず、そのようなモデルが未知または複雑な問題に適用可能である。このモデルフリーの特性は、明示的な遷移確率を必要とするモデルベースの手法と区別される。
応用と拡張
Q-learningは、ロボット工学、ゲームプレイ、および自律システムに応用されている。その表形式は小さな状態空間で機能するが、大きなまたは連続的な空間では、ディープQネットワークのような拡張がQ-learningとDeep learningおよびNeural network関数近似器を組み合わせる。これらの進歩により、Artificial intelligenceゲームエージェントやMachine learning制御タスクなどの分野での成功が可能になった。このアルゴリズムの原理は、BAIR (Berkeley AI Research)やMIT CSAILなどの機関での現代のReinforcement learning研究の基盤にもなっている。