Part1.

状態数が少なく、価値関数がメモリに乗るようなケースを考える。

主な手法

  • ベルマン方程式と動的計画法
  • モンテカルロ法
  • tempral difference

chap 2. Multi armed bandit

いわゆるバンディット問題を扱う。 kk個のアクションを選ぶことができて、アクションによって報酬の分布が決まる。 その分布に関する情報は持っていない。どのアクションを選ぶべきか？

アクションの価値を得られる報酬の期待値とする。 真の価値は分からないが、それまでに、そのアクションから得られた報酬の期待値で推定するのが自然。 アクション価値の推定値に基づいた戦略として

  • greedy
  • ε-greedy
  • UBC
  • Gradient Bandit

などが考えられる。

  • 報酬の分布は一定か
  • アルゴリズムのパラメータに対して、期待報酬はどう振る舞うか？

など検討すべきポイントがいくつかある。

chap3. Finite Markov Decision Process

MDPの定式化。

登場人物

  • エージェント
  • 環境

「環境が状態を提示→エージェントがアクションを選択→報酬を獲得」これが繰り返される

記号の定義

  • t=0,2,3,…t=0,2,3,…：時間
  • St∈S,t≤0St∈S,t≤0：時刻ttでの状態
  • At∈A(s),t≤0At∈A(s),t≤0：時刻ttでのアクション
  • Rt+1∈$⊂R,t≤0：時刻tのアクションから得た報酬

基本的に、これらは全部有限離散で考える。

p(s′,r|s,a)=Pr{St=s′,Rt=r|St−1=s,At−1=a}

という確率分布を指定してやれば、MDPが定義できる。

  • p(s′｜s,a)：状態の周辺分布
  • r(s,a)：報酬の期待値
  • r(s,a,s′)：報酬の期待値

などの表記も用いる。

MDPの枠組では、将来の報酬から計算される何らかの値を最大化することを考える。

ゲームなどのように、プロセスがいつか終わるようなタスクでは、開始から終了までの状態・アクション・報酬の列をエピソードと呼ぶ。

終わりのあるタスクでは、報酬の合計を最大化するのが自然。終わりのないタスクでは、将来の報酬を割り引いて合計した値を最大化するのが自然。

状態に対してアクションの確率分布を与える関数をポリシーと呼ぶ。 ポリシーが決まると、各状態において、そこから獲得できる報酬の期待値が決まる。これを価値関数(value function)と呼ぶ。 強化学習では、この価値関数の推定をするのが大事になる。

  • vπ(s)：ポリシーπに従うときに、状態sから得られる報酬の期待値。価値関数と呼ぶ
  • qπ(s,a)：ポリシーπに従い、状態sでアクションaを実行するときの、報酬の期待値。行動価値関数と呼ぶ

ポリシーπ,π′が、全ての状態sについてvπ(s)≤vπ′(s)を満たす時、π≤π′と定義すると、これは半順序になる。 この半順序について、最大値を達成するポリシーが常に1つ以上存在する。それを最適ポリシーと呼ぶ。 最適ポリシーが複数ある場合、その価値関数と行動価値関数は、常に同じ値となる。