問題
状態は一直線に並んだ $0,1,\dots,N-1$ の $N$ 個で、状態 $N-1$ をゴールとする。各状態には2つの行動 L（左へ1つ移動）と R（右へ1つ移動）があるが、この問題では学習中の行動選択は常にR（右移動）に固定されている（探索は行わない）。移動して着地した状態がゴールでなければ報酬 $-1$、ゴールに到達すれば報酬 $+10$ を得て、その回のエピソードは終了する。
すべての $Q(s,a)$ は $0$ で初期化する。学習率 $\alpha=0.5$、割引率 $\gamma=0.9$ は固定とする。エピソードは常に状態 $0$ から始まり、行動 R を選び続けてゴールに達するまで、以下のQ学習の更新式を状態を進めるたびに適用する。
$$Q(s,\mathrm{R}) \leftarrow Q(s,\mathrm{R}) + \alpha\Big(r + \gamma \max_{a'}Q(s', a') - Q(s,\mathrm{R})\Big)$$
ここで $s'$ は移動後の状態、$r$ はそのときの報酬。$s'$ がゴールの場合はエピソードが終了する（ブートストラップ項は使わず、ターゲットは $r$ のみ）。これを $K$ エピソード繰り返した後の $Q(0,\mathrm{R})$ の値を出力せよ。絶対誤差または相対誤差が $10^{-6}$ 以内なら正解とする。
入力形式
N K制約
入出力例
入力例1
4 3出力例1
-0.200000入力例2
4 10出力例2
5.768555概念図：報酬が1エピソードにつき1状態ずつ伝播する
ヒント（段階的開示）
ヒント1（方向性）
行動が常にRに固定されているなら、なぜ「行動$a'$について最大を取る」($\max_{a'}$)必要があるのか考えてみる。実際に選んだ行動はRだけでも、更新式のターゲット計算ではLの$Q$値も候補に入れて比較する。これがSARSAではなくQ学習（最良の行動でブートストラップする）である所以。
ヒント2（アプローチ）
1エピソードの中で状態を$0\to1\to\cdots\to(N-1)$と順に進めながら、その場で$Q(s,\mathrm{R})$を更新していく。次の状態$s'$の$Q$値を使うとき、そのエピソード内では$s'$自身の更新がまだ行われていないことに注意する。同じエピソード内では、報酬の情報は1ステップ分しか後ろに伝播しない。
ヒント3（誘導）
Q = {s: {"L": 0.0, "R": 0.0} for s in range(N)}
goal = N - 1
for episode in range(K):
s = 0
while s != goal:
ns = s + 1
if ns == goal:
reward = 10.0
target = reward # 終端状態はブートストラップしない
else:
reward = -1.0
target = reward + 0.9 * max(Q[ns]["L"], Q[ns]["R"])
Q[s]["R"] += 0.5 * (target - Q[s]["R"])
s = ns
print(f"{Q[0]['R']:.6f}")模範解答 (Python)
import sys
def main():
n, k = map(int, sys.stdin.read().split())
alpha, gamma = 0.5, 0.9
goal = n - 1
q = {s: {"L": 0.0, "R": 0.0} for s in range(n)}
for _ in range(k):
s = 0
while s != goal:
ns = s + 1
if ns == goal:
reward = 10.0
target = reward
else:
reward = -1.0
target = reward + gamma * max(q[ns]["L"], q[ns]["R"])
q[s]["R"] += alpha * (target - q[s]["R"])
s = ns
print(f"{q[0]['R']:.6f}")
main()Step-by-Step 解説
$s=0\to1$: target=-1+0.9×max(0,0)=-1, $Q(0,R)\leftarrow-0.5$。$s=1\to2$: $Q[2]$は未更新のためtarget=-1, $Q(1,R)\leftarrow-0.5$。$s=2\to3$(ゴール): target=10, $Q(2,R)\leftarrow5.0$。
下表の通り、$K=1$では$Q(0)$はまだ負のままだが、$K$を重ねるごとにゴール直前の高い価値が1エピソードにつき1状態ずつ左へ伝播し、$K=10$では$Q(0)$も正に転じる。
| K | Q(0,R) | Q(1,R) | Q(2,R) |
|---|---|---|---|
| 1 | -0.5 | -0.5 | 5.0 |
| 3 | -0.2 | 3.625 | 8.75 |
| 10 | 5.768555 | 7.904297 | 9.990234 |
Lは一度も選ばれないため$Q(s,L)$は常に0。序盤、ゴールから離れた状態の$Q(s,R)$はまだ負なので$\max(0,\text{負の値})=0$となり、本来伝播してほしい負の値ではなく0がブートストラップに使われる。よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| ゴール到達時もブートストラップ項を足してしまう | 終端状態の特別扱いを忘れる | $s'$がゴールのときはtarget = rewardのみとする |
| 同エピソード内で後の状態の更新結果を先の状態の更新に使う | 更新順序と参照タイミングの混同 | その時点で未更新なら未更新の値をそのまま使う（仕様であり、バグではない） |
| $\max_{a'}Q(s',a')$を「実際に次に選ぶ行動」の$Q$値と誤解 | Q学習とSARSAの混同 | Q学習は行動選択と無関係に、次状態で最良の行動の$Q$値を使う（オフポリシー） |
| 丸め誤差を気にして分数演算にしてしまう | 誤差許容($10^{-6}$)の仕様を見落とす | 通常のfloat演算で十分 |
L行動の$Q$値も更新されると思い込む | 「常にRを選ぶ」前提を読み落とす | $Q(s,L)$は初期値0のまま変化しない |
次のステップ
- 発展: 行動選択をε-greedyに変え、
LのQ値が動き出すと収束速度がどう変わるか実測してみる。 - 次回予告: Master Levelローテーション継続