強化学習の全体像まとめ

強化学習の全体像

RLmap

プランニング問題

環境が既知の場合の逐次的意思決定問題

$$ (B_{\star}v)(s)=\max_a{\pi(a|s)(g(s,a)+\gamma \sum p_T(s’|s,a)v(s’)} $$ $$ V^{\star}=\lim_{k\rightarrow \infty}(B_{*}^kV)(s) $$

$$ (B_{\pi}v)(s)=\sum_a\pi(a|s)(g(s,a)+\gamma \sum p_T(s’|s,a)v(s’)) $$ $$ V^{\pi}=\lim_{k\rightarrow \infty}(B_{\pi}^kV)(s) $$ $$ \pi(s)=\arg\max_a{g(s,a)+\gamma \sum_{s’}p_T(s’|s,a)V^\pi(s’)} $$

強化学習

環境が既知の場合の逐次的意思決定問題
報酬や次状態を観測することでデータを収集して，データから方策を学習する．

価値関数Vの推定

方策$\pi$を固定して価値関数の推定を行う．

$$ \hat{V}(s)=\hat{B}(\hat{V},h_T^\pi)(s) $$

  • TD法
    TD誤差$\delta$を計算して価値関数を更新する．

$$ \delta=r_t+\gamma \hat{V}(s_{t+1})-\hat{V}(s_t) $$

$$ \hat{V}(s_t)=\hat{V}(s_t)+\alpha_t\delta $$

  • TD($\lambda$)法
    エリジビリティートレースを用いて1エピソード分の価値を一括更新する．

行動価値関数Qの推定

方策$\pi$を固定して行動価値関数の推定を行う．

  • Q学習法
    価値ベース：maxを取っているため推定行動価値関数が方策に依存しない．

$$ \delta_t=r_t+\gamma \max_{a’}\hat{Q}(s_{t+1},a’)-\hat{Q}(s_t,a_t)
$$

$$ \hat{Q}(s_t,a_t)=\hat{Q}(s_t,a_t)+\alpha_t\delta_t $$

  • SARSA
    方策ベース

$$ \delta_t=r_t+\gamma \hat{Q}(s_{t+1},a’)-\hat{Q}(s_t,a_t) $$

$$ \hat{Q}(s_t,a_t)=\hat{Q}(s_t,a_t)+\alpha_t\delta_t $$

アクタークリティック法

アクターは行動を決定し，クリティックは環境から情報を集めることで状態の価値を推定し，これに基づき行動を評価を行う．

$$ \delta_t=r_t+\gamma\hat{V}(s_{t+1})-\hat{V}(s_t) $$

$$ \hat{V}(s_{t}=\hat{V}(s_t)+\alpha\delta_t $$

$$ q(s_t,a_t)=q(s_t,a_t)+\alpha\delta_t $$

*$q$は効用関数(価値観数は効用関数により得られる)

関数近似

状態数が膨大であったり，状態空間が連続の場合，計算量が多くなりすぎるため関数近似を行う．

価値関数近似

パラメータ$w$で規定される関数近似器を用いる．

  • 適合価値反復法(価値関数$V$)
    各経験の目的値を算出し，誤差最小化により$w$を求める．

$$ V_n^{target}=\hat{B}(\hat{V}_w)(s_n)=r_n+\gamma \hat{V}_w(s’_n) $$

$$ Q_n^{target}=\hat{B}(\hat{Q}_w)(s_n)=r_n+\gamma \max_a\hat{Q}_w(s’_n) $$

$$ w=\arg\min_w\frac{1}{N}\sum_1^N(V_n^{target}-\hat{V}_w(s_n))^2 $$

  • 適合Q反復法(行動価値関数$Q$)
    各経験の目的値を算出し，誤差最小化により$w$を求める．

$$ Q_n^{target}=\hat{B}(\hat{Q}_w)(s_n)=r_n+\gamma \max_a\hat{Q}_w(s’_n) $$

$$ w=\arg\min_w\frac{1}{N}\sum_1^N(Q_n^{target}-\hat{Q}_w(s_n))^2 $$

  • 近似TD法
    　TD誤差を再定義

$$ \delta = r_t + \gamma \hat{V}(s_{t+1}) - \hat{V}(s_t)$$

$\hat{V}_w$の $w$ に関する偏微分ベクトル

$$\nabla_w\hat{V}_{w_t}(s)$$

を用いて

$$ w_{t+1}=w_t+\alpha\delta_t\nabla_w\hat{V}_{w_t}(s_t) $$

  • 近似Q学習法

$$ \delta_t=r_t+\gamma\max_{a’}\hat{Q}(s_{t+1},a’)-\hat{Q}(s_t,a_t) $$

  • 近似SARSA法

$$ \delta_t=r_t+\gamma\hat{Q}(s_{t+1},a’)-\hat{Q}(s_t,a_t) $$

方策近似

  • 方策勾配法
    目的関数

$$ f_0=\sum_sp_{s_0}(s)V^{\pi_\theta}(s) $$

$$ f_\infty=\lim_{T \rightarrow \infty}\mathbb{E}[\frac{1}{T}\sum_{t=0}^{T-1}g(S_t,A_t)=\sum_{s}\sum_{a}p_{\infty}^{\pi_\theta}(a|s)g(s,a) $$

確率的勾配法に従い $$ \theta=\theta+\alpha_tG_t^\theta $$

  • モンテカルロ方策勾配法

$$ c_t=\sum_{k=t}^{T-1}r_k $$

$$ \theta=\theta+\alpha_n\frac{1}{T}\sum_{t=0}^{T-1}(c_t-b(s_t))\nabla_\theta \log\pi_\theta(s_t,a_t) $$

  • アクタークリティック方策勾配法
  • クリティックの更新
    推定平均報酬$f$の更新

$$f_t=f_{t-1}+\alpha_t(r_t-f_{t-1})$$

TD誤差の計算

$$ \delta_t=r_t - f_t + \hat{Q}w_{t}(s_{t+1},a_{t+1})-\hat{Q}_{w_t}(s_t,a_t) $$

エリジビリティ・トレースと関数近似器パラメータの更新

$$ z_t=\lambda z_{t-1}+\nabla_w\hat{Q}_{w_t}(s_t,a_t) $$

$$ w_{t+1}=w_t+\alpha_t\delta_tz_t $$

  • アクターの更新
    方策パラメータ$\theta$の更新

$$\theta_{t+1} = \theta + \alpha_t \hat{Q} (s_t,a_t) \nabla_\theta \log \pi_\theta(a_t|s_t)$$

参考文献

Tags: