強化学習入門

book rl

動機

PDFを見つけた, 強化学習 を知りたい

• 実装しないで理解したとは言えない. 理論と実装は表裏一体
  • なので擬似コードを付けた. 擬似コードは素晴らしい
• 2017までのアルゴリズム

概要

• 強化学習は教師あり学習と教師なし学習の中間のようなもの

• 生物学との結びつき
  • 行動戦略の買得
  • 群強化学習を用いた複数の生物モデルの迷路学習
    • ex. アリが餌のありかを情報伝達する

定義

簡単のため離散時間を想定

• $\mathcal{S}\subset {\mathbb{Z}}^d$: 状態空間

• $\mathcal{A}\subset \mathbb{Z}$: 行動空間

• $s_t\in \mathcal{S}$: 時刻 $t$ での環境

• $a_t\in \mathcal{A}$: 時刻 $t$ での選択した行動

• $\pi (a_t\mid s_t)\in [0,1]$: 状態 $s_t$ における方策=行動選択の確率

• $r_t\in {\mathbb{R}}^1$: 行動 $a_t$ によって得られた報酬

• $V^{\pi }(s_t)\in {\mathbb{R}}^{⊭}$: 方策 $\pi$ で状態 $s_t$ における価値

• $Q^{\pi }(s_t,a_t)\in {\mathbb{R}}^{⊭}$: 方策 $\pi$ で状態 $s_t$ において, 行動 $a_t$ の価値

• $\models$: 論理学では含意するの意

状態空間の例: 迷路

20x20の迷路を考えると各マスは上下左右のうち1-3個壁がある or ないで16-2通り, 状態空間は

$$\mathcal{S}=\{m\in {\mathbb{Z}}^{400}\mid 0\le m\le 13\}$$

行動は上下左右選べるので

$$\mathcal{A}=\{0,1,2,3\}$$

• 状態行動価値は状態と行動の2次元のテーブル Q-table とすることも多い

狙っている(適当な数字のプレースホルダーとして便利).

• 連続(= 次元数を高くすると)だと状態数が爆発して収束しない
  • 次元の呪い という.
• マルコフ性 : 時刻 $t+1$ の状態は $t$ によってのみ決められる
• マルコフ決定過程(MDP): マルコフ性を満足する強化学習

ベルマン方程式

ベルマン方程式: 強化学習の基本公式. 報酬を無限時間まで足し合わせると発散するので時刻に応じた係数(割引率) $\gamma \in {\mathbb{R}}_{0<\gamma <1}$ をかける.

$$V^{\pi }(s)=\mathbf{E}\left(\sum _{n=t}^{\infty }{\gamma }^{n-t}{r}_n;s_t=s\right)$$

価値とはその時刻以降で得られうる報酬の合計の期待値.

$$V^{\pi }(s)=\sum _{a\in \mathcal{A}}\pi (a\mid s_t)Q^{\pi }(s,a)$$

各行動での期待報酬を方策を重みとしてかけ, 足したもの

状態遷移確率 $P(s_{t+1}\mid s_t,a_t)$ を用いて, 漸化式にできて

$$V^{\pi }(s_t)=\sum _{a\in A}\sum _{s_{t+1}\in S}\pi (a\mid s_t)P(s_{t+1}\mid s_t,a)(r_t+\gamma V^{\pi }(s_{t+1}))$$

状態 $s$ で行動 $a$ をとった時の価値 = E(その行動の報酬 + 次状態で方策に従った行動の価値の和).

これの特殊な場合, 最適な方策 ${\pi }^{\ast }$ で行った時を考える.

• 最適な方策は迷いがないのである行動をとる確率が1でそれ以外が0 = 行動が決定的
  • $\sum$ を $\max$ に置き換えられる
• 動的計画法: 各時刻で最適行動を決定していく手法
  • 部分構造最適性(Optimal Substructure): ある問題を小さな問題に分割出来ること

3.6 モンテカルロ法

• 現実的には状態遷移確率がわかっているケースは多くない
  • わかっている: モデルベース
  • わかっていない: モデルフリー
• わからない時はたくさん試行して近似的な確率分布を得る
  • -> モンテカルロ法

$M$ 回のうち $m$ 回目の学習中, 状態列 $\{s_0,\cdots ,s_T\}$ に対して報酬列 $\{r_0,\cdots ,r_T\}$ を観測したとき,

• 初回訪問モンテカルロ法
  • 状態 $s_t$ が初めて出たなら収益を
    $R(s_t)+={\sum }_{t^{\prime }=t+1}^T{r}_{t^{\prime }},V(s_t)=\frac{1}{m}R$
    とする.
• 逐一訪問モンテカルロ法
  • 任意の時刻 $s_t$ で収益 $R(s_t)$ を導き, $V(s_t)$ を評価
• モデルフリーだと期待値が計算出来ないので状態価値 $V$ がわかっても行動が決定できない
  • 状態行動価値 $Q$ を計算してそれが最大のを選ぶとする
    • -> タプル $(s,a)$ が実際に観測されないと計算できない
      • 開始点探査(Exploring Starts)の仮定: モンテカルロ-ES法
        • 観測されない(=出る確率が0)ことはないと仮定する
      • 方策オン型モンテカルロ制御
        • 決定的な方策でなく確率的な方策にして, 任意のタプルで $\pi (s,a)>0$ を保証する
          • 確率的な方策 ex1. $ϵ$-greedy法
          • ex2. softmax法
      • 方策オフ型モンテカルロ制御

TD学習

• モンテカルロ法 は試行が終了するまで方策の更新が出来ない. それを回避したものが TD学習

• 1ステップTD法

• kステップTD法

• TD($\lambda$)法

参考文献

• 自分が読んだ強化学習の資料達 - 下町データサイエンティストの日常
• https://github.com/komi1230/Resume/blob/master/book_reinforcement/book.pdf
  • コミさん, 生物系の研究室でモデル生物の行動についての研究=機械学習していたらしい