Part1.

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

主な手法

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

chap 2. Multi armed bandit

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

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

  • greedy
  • ε-greedy
  • UBC
  • Gradient Bandit

などが考えられる。

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

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

chap3. Finite Markov Decision Process

MDPの定式化。

登場人物

  • エージェント
  • 環境

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

記号の定義

  • \(t = 0, 2, 3, \ldots\)：時間
  • \(S_t \in \mathcal{S}, t \le 0\)：時刻\(t\)での状態
  • \(A_t \in \mathcal{A}(s), t \le 0\)：時刻\(t\)でのアクション
  • \(R_{t+1} \in \mathcal{$} \subset \mathbb{R}, t \le 0\)：時刻\(t\)のアクションから得た報酬

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

\[p(s', r | s, a) = \mathrm{Pr}\{S_t=s', R_t=r | S_{t-1} = s, A_{t-1} = a \}\]

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

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

などの表記も用いる。

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

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

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

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

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

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