次元の呪い（Curse of dimensionality）

強化学習の一つの問題に次元の呪いがある。これは、状態数が指数関数的に増大する傾向のことを指す。ほとんどの問題では、状態数が大きすぎて、表形式（配列でQ[S][A]のように価値関数を表す方式）で管理することができなくなる。前にやった迷路はそんなに大きくないので、表形式でできた。

しかし、tic-tac-toeは、○と×があって、置けるところが9個あるから、単純計算で2の9乗くらいある。これでも一般的な問題に比べて全然大きくないが、500個近い配列（しかもその大部分は使わない）を用意しておくのは無駄である。

このようなときには、関数近似という手法を使うのが一般的らしいが、tic-tac-toeで参考にした Sutton, Barto のプログラムはハッシュ法を使っていて少し違うように思っていたのだがやっとわかった。『強化学習』（p.223）にハッシュ法で次元の呪いを解決する話が載っていた。簡単な例だけど実例があると理解がずいぶん早まる。ニューラルネット、タイルコーディングなどもっと複雑な関数近似法もあるので順次調べていく。タイルコーディングは、倒立振子制御に使われているように見受けられる。概念は同じなのに時代によって名前が違う（それとも似ているだけで実質違うのか）ので混乱しがちになっている。