TD法はなぜうまくいかないのか

宇宙の熱的死を認めるなら、十分大きい時間が経過したときの宇宙の巨視的な状態の分布はエルゴード性を満たす(単一状態しかないから)。
いやそこまで風呂敷を広げずに二人零和有限確定完全情報ゲームに話を限ろう。この場合も同様に、

• 対戦者同士が常に同じような傾向で手を打ってくる(例えば、常に最善手を打つ等)

という条件下で十分大きい時間スパンで見れば、ある局面に対して打たれる手の分布はエルゴード性を満たす。常に最善手を打つ対戦者同士だとマルコフ性も申し分無い。最善手を打ってくるとは限らず確率的でも、よほど偏屈で無限の記憶を持つような相手でもなければマルコフ性が成立すると見ていいはずだ。また局面数は有限だから、測度的にも問題が無い。
だから将棋とかTD学習の格好の対象ですよ奥さん！
だがちょっと待って欲しい。我々は神ではないから相手の打ってくる手の分布は経験的確率を通してしか知りようがない。相手の手の分布が経験的確率上一定に収束してエルゴード性が確認されるまでに、一体何試合こなさねばならないのか？エルゴード性が確認されるまで、我々は次々新たな手筋が編み出されて経験的確率が変動し続けるのを指をくわえて見ているしかないのではないか？そして将棋の局面は10^220個もあり、打てる手筋はそれ以上のオーダーで存在するのだ。

だからTD法を適用可能にするには次のどちらかの方策が必要だ(両方でもいい)。

1. 経験確率が十分短時間で収束するようにゲームに現れる局面の数を制限する
2. 経験確率が変化していく条件でも学習が何らかの最終状態分布に向かってできるだけ単調に漸近するように構成する

これを達成してなお状態の爆発を防がねばならない。微妙な差異しかない2つの事象に異なる状態を割り当て、それぞれ毎に行動の期待報酬を記憶するやり方ではすぐに空間を使い果たしてしまう。例えば将棋の局面は10^220もあるからそれの1個1個を状態と見なすわけには行かない。「同じとみなすべきものを同じに扱う」強力な汎化器が別途必要だ*1。

経験確率が十分短時間で収束するようにゲームに現れる局面の数を制限するには

進行度に基づく力学のようなものを考える。
敵が攻勢を続けるときに防御ばかりしていては手が遅れて負けるから、その意味で実際には生じない局面が言える。
だがこの考えが現実に機能するには、ほとんど物理的な意味を持つと言っても良いような確固とした局面評価手法が必要なのだ以下略

経験確率が変化していく条件でも学習が何らかの最終状態に向かってできるだけ単調に漸近するように構成するには

秘密。まあ状態の爆発を防ぐ話と被る。

状態の爆発を防ぐには

秘密。9月以降の成果をそのうち見よ。

追記

ここ数ヵ月間のGMA0BNの脳内ではあまりに当然なことになりすぎて思わず書き忘れましたが、TD法で手を学習させるとは言ってませんからね。

*1:上述の局面の数の制限が実現しても将棋の複雑さから言って数十や数百の局面に押さえ込めるとは考えがたいから、この点は変わらない。