強化学習
たとえ探索の問題を無視して、状態が観測可能であっても(以下は仮定)、過去の経験を使用して、どの行動がより高い累積報酬につながるかを見つけ出すという問題が残される。
ほとんどのアルゴリズムの漸近的挙動と有限標本挙動の両方がよく理解されている。(探索問題に対処する)優れたオンライン性能が証明されたアルゴリズムも知られている。
MDPの効率的な探索については、Burnetas and Katehakis(1997)で述べられている。また、多くのアルゴリズムで有限時間性能の限界が見られるが、これらの限界はかなり緩いと予想されるため、相対的な価値と限界をより深く理解するために、さらなる研究が必要である。
インクリメンタルアルゴリズムについては、漸近的収束の問題が解決された。時間差分に基づくアルゴリズムでは、従来よりも広い条件の下で収束するようになった(たとえば、任意の滑らかな関数近似と併用する場合)。
勾配の解析式が存在しないため、ノイズを含んだ推定値しか利用できない。このような推定値はさまざまな方法で構築することができ、ウィリアムズのREINFORCE法(シミュレーションベース最適化(英語版)の文献では尤度比法として知られている)のようなアルゴリズムで作成することができる。方策探索法は、ロボット工学の文脈でも使用されている。多くの方策探索法は、局所最適に陥ることがある(局所探索に基づいているため)。
勾配情報への依存を避けるために、多くの種類の方法がある。たとえば、シミュレーティドアニーリング、クロスエントロピー探索(英語版)、または進化的計算の手法などがある。多くの勾配を用いない手法は、(理論的にも極限的にも)大域的な最適解に到達することができる。
ノイズの多いデータでは、方策の収束が遅くなることがある。こうしたことは、たとえば、軌跡が長くリターンの分散が大きい偶発的問題で起こる。このような場合、時間差分法に依存する価値関数に基づく手法が役立つ可能性がある。近年では、アクター・クリティック法(actor-critic methods)が提案され、さまざまな問題で良い結果を出している。