多腕バンディット問題の解（Dynamic Programming)

多腕(k)バンディット問題をDirect programmingで解きます。
現在の状態sについて、将来の最大期待値であるV(s)は下記のように書け、
下記を満たすようなアームjを選択するのが、次の一手になります。

ここで、

V(s)は、全てのアームについてこれまで得られた情報sから考えられる最大期待値

Rj(sj)は今、アームjを選んだ時に直ちに得られる報酬

si (i = 1, 2,..k)は、k個のスロットそれぞれについてのこれまでの情報（成功、失敗）

s'はそれから一つアクションをおこした時の情報（jが選ばれたらs'j）

γは将来に対しての割引率です。

この式の大切なところは、V(s)が、これまで得られた情報sと、
一アクション進んだ時の最大期待値であるV(s')で直接計算できることです。

つまりT回引くと最初に決まっていれば、最後の時点での
V(last) =０と置いておけば、その一個手前のV(last-1)は、
どれか一つが選ばれる前の可能性として求められ、、、
と逆算逆算によって、V(s)が直接求められます。

問題は、Tと、kの数によって計算量が指数的に増えていくところです。

これに解決策を与えるために色々な方法があります。

Gittins Indexについて次は書いてみたいと思います。