価値の定義と算出 Bellman Equation

価値を再帰的かつ期待値で表現する手法をBellman Equationと呼びます。(Valueベース)
Bellman Equationを使えば各状態の価値が計算可能となります。

まず価値を返す関数を定義します。

1
2
3
def V(s, gamma=0.99):
V = R(s) + gamma * max_V_on_next_state(s)
return V

報酬関数を定義します。
エピソード終了のとき”happy_end”であれば1を返し、”bad_end”であれば-1を返します。
エピソードが終了していなければ0を返します。

1
2
3
4
5
6
7
def R(s):
if s == "happy_end":
return 1
elif s == "bad_end":
return -1
else:
return 0

全ての行動でV(s)を計算し値が最大になる価値を返します。
評価vの計算式は確率遷移×遷移先の価値となります。

upかdownかを繰り返していき5回行動したら終了となります。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def max_V_on_next_state(s):
# If game end, expected value is 0.
if s in ["happy_end", "bad_end"]:
return 0

actions = ["up", "down"]
values = []
for a in actions:
transition_probs = transit_func(s, a)
v = 0
for next_state in transition_probs:
prob = transition_probs[next_state] # 確率遷移
v += prob * V(next_state) # 遷移先の価値
values.append(v)
return max(values)

遷移関数を定義します。

  • 引数sには”state”や”state_up_up”、”state_down_down”などが受け渡されます。
  • 引数aは”up”か”down”が設定されます。
  • エピソード完了時は1要素が返り、途中の場合は2要素が返ります。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def transit_func(s, a):
actions = s.split("_")[1:]
LIMIT_GAME_COUNT = 5
HAPPY_END_BORDER = 4
MOVE_PROB = 0.9

def next_state(state, action):
return "_".join([state, action])

if len(actions) == LIMIT_GAME_COUNT:
# 最大行動数と一致するのでエピソード終了
up_count = sum([1 if a == "up" else 0 for a in actions])
state = "happy_end" if up_count >= HAPPY_END_BORDER else "bad_end"
prob = 1.0
return {state: prob}
else:
opposite = "up" if a == "down" else "down"
return {
next_state(s, a): MOVE_PROB,
next_state(s, opposite): 1 - MOVE_PROB
}

実際に価値V(s)の計算を行ってみます。

1
2
3
4
if __name__ == "__main__":
print(V("state"))
print(V("state_up_up"))
print(V("state_down_down"))

実行結果

upの数が多い方が評価されます。

参考

Pythonで学ぶ強化学習 -入門から実践まで- サンプルコード