無限期間動的計画法について
グレーヴァ香子
一人の意思決定者が、以下のように行動a1, a2, . . .を選んで無限期間の報酬の割引和 u(a1;s1) +δu(a2;s2) +δ2u(a3;s3) +· · ·=
X∞
t=1
δt−1u(at;st) を最大にするという問題を考える。
1. 初期状態s1が決まる。行動a1 ∈A(s1)を選ぶと報酬u(a1;s1)を得る 2. 状態s2が決まる。行動a2 ∈A(s2)を選ぶと報酬u(a2;s2)を得る。
3. 状態s3が決まる。行動a3 ∈A(s3)を選ぶと報酬u(a3;s3)を得る。
· · ·
一般には、状態の変化は意思決定者の過去の行動すべてと過去の状態全てに依存する。また、
意思決定者は各期の状態によって行動を変えることができるので、展開形ゲームの戦略を決め ると考えることができる。ゲームと解釈するときは、状態は過去の全てのプレイヤーの（観察 された）行動の列と考えられる。xを戦略とし、第１期の行動は条件付きでないのでx1と書く ことにする。その後の行動はxとその期の状態によって決められる条件付き行動である。各期 の状態と行動は以下のように決まっていくと考える。（状態の変化は仮定。行動は純戦略を用い るとこうなる、ということ。簡単化のため、行動の集合At(st)はすべて有限集合と仮定する。）
s2 =s2(x1, s1), a2 =a2(x, s2(x1, s1)) s3 =s3(x1, a2, s1, s2(x1, s1)), a3 =a3(x, s3(x1, a2, s1, s2)
· · · · · ·
簡略化して書くと
st =st(x, s1), at=at(x, s1) とすることができる。
定義：報酬の割引和をValue functionといい、初期状態s1の下で、戦略xを選んだとき、以下 のように定義する。
V(s1, x) = X∞
t=1
δt−1u(at(x, s1);st(x, s1))
戦略xを選んでValue functionを最大にしたものを Optimal value functionといい、
f(s1) = sup
x
V(s1, x) と書く1。
1戦略が無限個あるので、maxが存在するとは限らないが、最小上界(sup)は存在する。ある集合Xについて、
その最小上界supXとは、「全てのx∈Xについてy=x」となるyの中で最小のもの。
1
Bellman Equation
定理：Optimal value functionfは以下の式(Bellman Equation)を満たす。
f(s1) = max
a1∈A(s1)
h
u(a1, s1) +δf(s2(a1, s1)) i
.
証明：まず左辺≤右辺を示す。
任意の戦略xについて、定義よりValue functionは以下の式を満たす。
V(s1, x) =u(x1, s1) +δV(s2(x1, s1), x).
V(s2(x1, s1), x)≤supaV(s2(x1, s1), a) =:f(s2(x1, s1))であるから V(s1, x) ≤ u(x1, s1) +δf(s2(x1, s1))
≤ max
a1∈A(s1)[u(a1, s1) +δf(s2(a1, s1))].
xは任意だったから、
supxV(s1, x) = f(s1)≤ max
a1∈A(s1)[u(a1, s1) +δf(s2(a1, s1))].
次に、左辺≥右辺を証明する。
a∗1として、今日の報酬と、明日からは最適になっているとしての報酬の和を最大にする（以 下の式を満たす）ものをとる。
u(a∗1, s1) +δf(s2(a∗1, s1)) = max
a1∈A(s1)[u(a1, s1) +δf(s2(a1, s1))].
sup の定義より、任意の状態sと任意の（小さい）² > 0について、戦略a0(s)が存在して V(s, a0(s))≥f(s)−²とすることができる。
戦略aとして、１期目はa∗1を、２期目以降はa0(·)に従うものを考えると V(s1, a) = u(a∗1, s1) +δV(s2(a∗1, s1), a0) f(s1)≥V(s1, a) ≥ u(a∗1, s1) +δf(s2(a∗1, s1))−δ².
a∗1の定義より
f(s1)≥ max
a1∈A(s1)[u(a1, s1) +δf(s2(a1, s1))]−δ².
²→0としても、等号付きの不等式は成立するので f(s1) ≥ lim
²→0
h
a1max∈A(s1)[u(a1, s1) +δf(s2(a1, s1))]−δ² i
f(s1) ≥ max
a1∈A(s1)
h
u(a1, s1) +δf(s2(a1, s1))i .
2
