この記事は何？
友達と強化学習の本を読む機会があり，毎週1章ずつ勉強しています．そこで学んだことをアウトプットしたものです．
今回は2章のまとめです．短い時間で書いているため，拙い部分も多くありますがご容赦下さい．
とりあえず公開して，更新していくことが大事だと考えています
2章 マルコフ決定過程
「1章 バンディット問題」では，エージェントがどのような行動をとっても次に取り組む問題は変わりませんでした．エージェントは毎回同じスロットマシンに取り組み，常に最善のスロットマシンを探します．
でも，現実の問題はエージェントの行動によって環境が刻一刻と変化します．例えば車を運転していると，アクセルを踏んだりハンドルを切ったりするたびに交通状況は刻一刻と変化します．囲碁についてもエージェントがある手を打つと盤上の石の配置は変わり，環境が変わります．エージェントは状況が遷移することを考慮して最善の手を打つことがもとめられます．
本章ではこのようにエージェントの行動によって状況が遷移する問題を扱います．これらのうちの一部はマルコフ決定過程(Markov Decision Process) と呼ばれます．
2.1 MDPとは
2.1.1 MDPの具体例
- 1~5までの5つのマスが横並びになったグリッドワールドを考える
- エージェントは最初3のマスにいる
- エージェントは「右に1進む」または「左に1進む」の2種類の行動をとることができる
- １のマスにはリンゴ，5のマスには爆弾が置かれている
- リンゴを取った時の報酬は+1，爆弾をとった時の報酬は-2である
エージェントが動くとエージェントが置かれる状態は変わります．この場合は，エージェントにとって最適な行動は左に2回進むことです．
でも，4のマスに爆弾があって，5のマスにリンゴが6個あることもあります．その場合は爆弾を踏んでもリンゴ6こを撮りにいく方がいいです．エージェントは目先の利益だけではなく，報酬の総和を最大化することが求められます．
2.1.2 エージェントと環境のやりとり
時刻$t$において，状態が$S_t$であることを考えます．エージェントは行動$A_t$を行い，報酬$R_t$を受け取り，状態$S_{t+1}$に遷移します．
2.2 定式化
MDPを定式化するには以下の3つを定式化する必要がある
- 状態遷移: 状態がどのように遷移するか
- 報酬: 報酬はどのように与えられるか
- 方策: エージェントはどのように行動を決定するか
順にやっていきます．
2.2.1 状態遷移
状態遷移には2通りあります．
- 決定論的: エージェントが行動を選択したら，必ずその行動が行われる
- 確率的: エージェントが行動を選択しても，その行動が行われない場合がある．
確率的挙動の場合は，エージェントが「左へ行く」と決定しても右に動くことがある．その原因は床が滑るといった環境の場合もあるし，モーターが誤作動するといった内部要因かもしれない．
決定論的遷移の場合の定式化:
$$s' = f(s, a)$$
現在の状態と行動がわかれば，次の状態$s'$は決定できる．
確率的遷移の定式化:
$$p(s'|s, a)$$
状態$s$にいて，行動$a$をとった時に状態$s'$に遷移する確率
重要な性質として，状態遷移は現在の状態$s$と行動$a$だけに依存する．つまり，現在より過去の情報は必要ない．このような性質をマルコフ性と言う．この性質を仮定しないと問題が複雑すぎて解けない．
2.2.2 報酬関数
本章では報酬は決定論的に与えられるとする．
$$r = r(s, a, s')$$
報酬は現在の状態，現在とる行動，次の状態が決まれば決まる(マルコフ性の仮定)．
報酬は確率的に与えられる場合もあるが，その場合も報酬関数$r(s, a, s')$を「報酬の期待値」を返すようにすれば決定論的に扱える．
2.2.3 方策
方策も決定論的な場合と確率的な場合があります．
- 決定論的方策: 現在の状態$s$に応じて，とる行動は1通りに決まる．
- 確率的方策: 同じ状態$s$においても，とる行動は1通りでない．
決定論的方策の定式化::
$$a = \mu(s)$$
現在の状態がわかれば，とる行動も決まる．
確率的方策の定式化:
$$\pi(a|s)$$
状態$s$にいるとき，行動$a$をとる確率．
決定論的方策も確率的方策の1種である．決定論的方策は，状態$s$において，行動$a$をとる確率が1，それ以外の行動をとる確率が0である確率分布の見なすことができる．
2.3 MDPの目標
MDPの目標は収益を最大化するような**最適方策(Optimal Policy)**を見つけること．ここでは最適方策を厳密に定式化するための準備を行う．
まずは，MDPが2つに分けられることを説明します．「エピソードタスク」と「連続タスク」です．
2.3.1 エピソードタスクと連続タスク
- エピソードタスク: ゲームのように終わりがあるタスク
- 連続タスク: 在庫管理のような，終わりがなく永遠に続くタスク
2.3.2 収益
将来得る収益の重みつき和．エージェントが時刻$t$で方策$\pi$によって行動$A_t$を取り，報酬$R_t$を受け取って状態$S_{t+1}$に遷移するとする．収益$G_t$は
$$G_t = R_t + \gamma R_{t+1} + \gamma^2 R_{t+2} + \cdots$$
$\gamma$は割引率と呼ばれ，収益が無限大に発散することを防ぐとともに，「近い将来の報酬の重要性を増す」と言う行動原理を実現している．
2.3.3 状態価値関数
エージェントと環境が確率的に振る舞う可能性があるため，収益はエピソードによって変わる．よって，収益も期待値を通して評価する必要がある．これを状態価値関数と呼ぶ．
$$v_{\pi}(s) = \mathbb{E}[G_t|S_t = s, \pi]$$
状態$S_t$が$s$であり，エージェントの方策は$\pi$であることが条件．$v_{\pi}(s)$は状態と方策によって決まる，各状態の価値．そのまますぎる．
2.3.4 状態価値関数と最適方策
MDPの目標は最適方策を得ることだったが，「最適」とはどのように表すのだろうか？
最適方策の定義は，すべての状態について状態価値関数が最大となる方策のこと．つまり，どの状態にいる場合も状態価値関数が最大となる方策のこと．
MDPにおいては最適方策が少なくとも1つ存在し，しかもそれは決定論的方策であることがわかっている．この方策を数式で$\mu_*{s}$と表す．行動は
$$a = \mu_*(s)$$
のように状態に応じて1つに決まる．
2.4 MDPの例
2マスのグリッドワールドで，右端と左端に壁がある．左側のマスをL1，右側のマスをL2と呼ぶ．
- エージェントは、右と左のどちらかに移動することができる
- 状態遷移は決定論的とする(エージェントが右へ進む行動を行うと、エージェ
ントの次の状態は必ず右側へ移動する) - エージェントが L1 から L2 へ移動したときにリンゴを受け取り +1 の報酬を
得る - エージェントが L2 から L1 へ移動するとリンゴが再度出現する
- 壁にぶつかると −1 の報酬を得る(罰を受ける)。たとえば、エージェントが
L1 にいて左へ進む行動を行った場合には −1 の報酬を得る。また、状態 L2 で右へ進む場合も同様に −1 の報酬を得る(このとき、リンゴは出現しないこ とにする) - 今回は連続タスクとして「終わり」のない問題設定とする
この問題においては，方策はすべて書き出すことができる．最適な方策は
- $s = L1$であるとき: 右に動く
- $s = L2$であるとき: 左に動く
である．こうするとリンゴを永遠に受け取り続けることができる．これは決定論的方策．