Q 学習

Q 学習は、状態で行動を取る価値を経験から推定します。一遷移で更新する Q 表は一項だけで、観測報酬と次状態の最大推定値を使います。再訪によって遅れた報酬が前の選択へ伝わり、環境の遷移モデルを事前に知る必要はありません。

分岐の標識を考えてください。報酬出口に着くと最後の矢印が変わり、前の分岐は後の訪問で改善済みの標識を読めます。報酬が全経路を一度に書き換えるわけではありません。本課は次の一手の +1 と三手先の +5 を比べます。地図は読者に見えますが、更新器は経験した移動だけを使います。

一経験で一推定を変更

状態は位置、行動は合法な移動です。環境は即時報酬と次状態を返します。Q(s,a) は a を選び、その後最適方策に従う割引収益の推定で、初期には誤りえます。行動確率ではありません。

エピソードは出発から出口までで、次の開始は位置だけ戻し表を保ちます。観測 (s,a,r,s') に対し：

future = max over legal a' of Q(s', a')
target = r + gamma * future
Q(s, a) <- Q(s, a) + alpha * (target - Q(s, a))

r は観測済み、future は推定です。target − Q(s,a) は時間差分誤差。本課の alpha = 0.5 は目標へ半分進め、低い目標なら Q を下げます。終端の future はゼロで、出口報酬は既に r にあるので二重加算しません。他の項は不変です。

割引と探索

gamma は遷移ごとに掛かります。三手目の 5 は出発時収益へ gamma² × 5、gamma = 0.9 なら 4.05。一手目の 1 は割引しません。gamma ゼロは即時報酬だけです。変更は速さだけでなく目的の変更です。

epsilon-greedy は epsilon の確率で合法行動を一様抽出し、残りは最大 Q を選びます。乱数でも最大行動を引けるため、探索は抽出方法であって劣る行動の保証ではありません。

Q 学習はオフポリシーで、行動方策が次に別行動を引いても目標は次状態の最大値です。SARSA は実際に抽出した次行動を使うオンポリシー目標で、異なる方策の問いを扱います。

ステップ実行

既定の二行三列です。

S の合法順は上・右、A は右・左、B は上・左。出口へ入ると報酬を受けて終了し、他の移動はゼロです。壁や外側の行動はダッシュで、ゼロ推定ではありません。

合法 Q は全ゼロ、alpha = 0.5、epsilon = 0.35、gamma = 0.9、八エピソード、種子 947。同点は上の順なので最初の貪欲選択は上です。八遷移で打ち切りますが、既定の最長は五なので影響しません。

エピソード 1：S から上で 1、終端 future ゼロ、目標 1。Q(S,上) = 0 + 0.5×(1−0) = 0.5、右はゼロです。

2：探索で右の A へ。報酬と A 推定はゼロで S 右は不変。A から B も目標ゼロ。B 上で初めて 5 を受け、Q(B,上) = 2.5。前二項は既に更新済みで自動的に戻りません。

3：S から A の目標はまだゼロ。A から B は Q(B,上) = 2.5 を読み、目標 0.9×2.5 = 2.25、Q(A,右) = 1.125。再び目標へ着き B 上は 3.75 になります。

4：探索で S 右。A の最大 1.125 から目標 1.0125、Q(S,右) = 0.50625 となり上の 0.5 を僅かに超えます。貪欲矢印は右へ変わり、目標まで進みます。

各標識は自分の行動を再び試して変わります。最初の報酬前に S と A はゼロ目標で更新済みだったので、次の訪問が必要です。

5：S → A → B → A → B → 目標。最初の A→B で B 上は 4.375、左はゼロなので目標 3.9375、A 右は 2.25 から 3.09375 へ。その次の探索は B 左を選びます。目標は最良継続を使い、行動は寄り道しました。抽出した左を目標に使うならゼロとなり、同じ前半でも A 右は 1.125 になります。

6–8：直行経路を繰り返し、最後の S 右は約 3.27480、上は 0.5。選択は改善しても推定は完全ではありません。

最後は表を凍結し探索を除き、S → A → B → 目標 で割引収益 4.05 を得ます。実行収益と推定 3.27480 は別です。有限実行は価値伝播を示し、収束を証明しません。

表が向く場面

状態と合法行動を列挙し、再訪できる小問題に向きます。必要なのは遷移で、正解行動ラベルではありません。遷移と報酬が既知なら直接計画できるため、その費用と経験収集の費用を比較します。

epsilon は経験収集、gamma は遅れた報酬の重みです。速く見せるため gamma を下げると別問題になります。探索学習と凍結した貪欲評価を分け、乱数の寄り道を方策の好みと混同しません。

計算量

S 状態、最大 A 合法行動なら空間 O(SA)。線形走査の貪欲選択や次状態最大は O(A)、一項更新は O(1)、T 遷移で O(TA)。本図は三非終端状態・各二行動なので一回は定数です。

有用な方策に必要な経験数は別で、報酬発見が表更新よりずっと高くつく場合があります。表示スナップショットは基本アルゴリズム外の記憶です。連続・巨大状態では各対の表が非現実的になり、関数近似で共有できますが別の学習問題を加えます。

境界ケース

• 探索なし：epsilon 0、gamma 0.9 はゼロ初期化と同点順で八回とも小出口。S 上は約 0.99609、右ゼロ。試さない行動の証拠は得られません。
• 即時だけ：gamma 0、epsilon 0.35 では大目標を見ても A 右と S 右はゼロ、最後 S 上は 0.9375。上の選択はこの目的に合います。
• 常に探索：epsilon 1 は全行動をランダム化しても目標は最大値、最後は貪欲評価です。八回で十分な経験を保証しません。
• 終端と打切り：出口は future ゼロ。八遷移上限は環境を終端にせず、最後も非終端 bootstrap を使います。凍結方策が状態を繰り返すと循環を報告します。
• 同点：固定順は再現のためで、ランダム破同点なら別の経験になります。

よくある間違い

• Q を最後の即時報酬と読み、将来推定を落とす。
• 報酬が来たら全前段を更新する。一段 Q 学習は経験した一対だけで、前段は再訪が必要です。
• r と終端 bootstrap へ出口報酬を二度入れる。
• 不可行動を最大値へ含める。ダッシュは全合法値が負でも argmax に入りません。
• 探索軌跡を凍結貪欲方策と呼ぶ。
• 八成功エピソードで最適性を主張する。十分な反復標本と適切な学習率が必要で、短い固定 alpha はその証明になりません。Watkins と Dayan の論文を参照してください。

モデルの範囲

決定的な格子、状態別合法行動、表、固定学習率、選んだ種子、短い予算です。確率的遷移、大状態空間、深い Q 学習の関数近似、経験再生、目標ネットワークは省略します。地図は見えても更新則は標本だけを使い、既知モデルで計画しません。