2章マルコフ決定過程

バンディット問題では、エージェントがどのような行動を取っても、次に取り組む問題は変わりません。エージェントは毎回同じスロットマシンに挑み、その中で最善のスロットマシンを探します。しかし現実にある問題は違います。たとえば、囲碁について考えてみましょう。囲碁では、エージェントがある手を打つと、盤上の石の配置が変わります（そして対戦相手が石を打ち、さらに盤上の石の配置は変わります）。このようにエージェントの行動によって状況は刻一刻と変わります。エージェントには、状況が遷移することを考慮して、最善の手を打つことが求められます。

前章では、スロットマシンの報酬設定（報酬の確率分布）が時間の経過とともに変わる「非定常問題」についても説明しました。非定常問題は、エージェントの行動に関係なく、時間の経過とともに「報酬の確率分布」が変わります。ここで考えるのは、エージェントの行動によって環境の状態が変化する問題です。

本章では、エージェントの行動によって状況が変わる問題を扱います。そのような問題の一部はマルコフ決定過程（Markov Decision Process、略してMDP）として定式化されます。本章では初めにMDPで登場する用語を説明し、数式を使って表します。その後でMDPの目標を明確にした上で、実際にMDPの簡単な問題を示しながら目標を達成する過程を見ていきます。