Reinforcement learning book

対象: 学部 3, 4 年生，大学院生

Reading

英語の教科書の読み方を，外国語論文講読等の授業で扱います． 強化学習の分野の有名な教科書を読んでみましょう．

教科書: 書籍だけでなく，PDFでの配布もあるので，自宅での学習もしやすいと思います．
Reinforcement Learning: An Introduction

以下，予習の参考に．

questions

Chapter 1

単語: interaction, mapping, trial-and-error, delayed reward, labeled examples, generalize, hidden structure, trade-off, uncertain environment, perceived state, imperfect player, planning, lookahead, opponent, discrete time steps, tabula rasa

1.1

  • 強化学習 (以下RL) は，(計算機が) 何を学ぶものでしょう?
  • RLの2つの特徴は何でしょう?
  • supervised learning と RL の違い，unsupervised learning と RL の違いは，それぞれどのような点でしょう?
  • RL ならではの特徴は，どのようなものがあげられていますか?

1.2

  • 様々な例に共通する特徴を確認してください

1.3

  • RL における，主要な4つの要素は何でしょう
  • RL で学ぶエージェントの，学習の目標を上記の言葉で説明してください
  • reward と value の違い，reward 最大の action と，value 最大の action の違いは何でしょう

1.4

  • (evolutionary methods については，初見なら当座は無視して良い)

1.5

  • tic-tac-toe (三木並べ)は探索で両者最善にプレイしたときの解が求められる．これを強化学習で学ぶ意味は何か? (どのような前提が設定されているか)
  • Fig. 1: グラフの各要素と記法を説明してください
  • 次式の直感的な意味を説明してください $$ V(S_t) \gets V(S_t) + \alpha\left[V(S_{t+1}) - V(S_t)\right] $$

Chapter 2

  • 概念: value, greedy, epsilon-greedy, action-value estimates, stationary, noisier rewards, constant memory, exponential recency-weighted average, biased, prior knowledge
  • 用語: converge, sophisticated methods, performance, run, sample-averag, initial conditions, random fluctuations, optimistic, natural logarithm, associate

全体

  • 冒頭で比較されている， evaluates と instructs の違いについて，直感的に説明せよ
  • 3章以降と比較した，この章の位置づけは?
  • 数学記号で表されている各概念について，エージェントに見えている情報と，エージェントに見えていない情報 (世界の管理者=実験設計者のみ見えている)，定義はできるが計算できるとは限らないもの，などに分類せよ

2.1

  • この章では， random variable とそうでないものの両方が登場する．どれが random variable か?
  • $k$-armed bandit problem とはどのような問題か．
    • 関連の深そうな現実の問題を1つあげよ
    • (現実性はなくて良いので) 具体的な問題を1つ (誤解の余地のないような記法で) 定義せよ．
  • $k$-armed bandit problem での agent の目的は?
  • greedy actions/exploiting/exploring とは，この問題ではどのようなaction (をとること) をさすか?

2.2

  • 以下の記法の日本語の呼び方を調査せよ \( \mathbb{1}_\text{predicate} \)
  • 以下の記法の意味を，簡単な例とともに説明せよ \( \arg\max_a \)

2.3

  • Fig. 2.1 を説明せよ．
    1. これは大きく言うと何か (e.g., 問題設定，学習結果)，
    2. 縦軸と横軸の意味，灰色部分の面積の意味，
    3. エージェントに見えているものは何か
  • Fig. 2.2 を説明せよ
    • グラフの意味
    • 何をすればこのグラフを書けるか (能力が十分なプログラマに指示すると仮定して，明確に要件を伝えよ)
    • 各色の線の差について，手法と整合する理由を説明せよ (i.e., 運が超悪かったから，とかは除く)

2.4

  • incremental implementation は，そうでない場合と比べて，何が得か?

2.6

  • optimistic であることが agent にとって 得 になるのはどのような状況か?
  • optimistic であることが agent にとって 損 になるのはどのような状況か?
  • optimistic である方が総合して得なことが多いと考える理由は?

2.7

  • この節と 2.2 Action Value Methods との関係は?
  • 式 (2.10) で $c=0$ だった場合は，どのような振る舞いをするか．また $c$ の項の平方根の中は，どのような増減をするか

2.8

  • この節と 2.2 Action Value Methods との関係は?
  • 式 (2.12) の stochastic gradient ascent について，検討せよ．たとえば，符号はこれで良いのか，反転させるとダメなのか?
  • (後回しでも良い) 最後の囲みの末尾付近の以下の引用部分を 式で確認せよ

    the choice of baseline does not affect the expected update

Chapter 3

概念: episodes, terminal state, episodic tasks, continuing tasks, expected return, discounted return, policy, (optimal) state-value function, (optimal) action-value function
単語: unique solution, equation

  • この章でも， random variable とそうでないものの両方が登場する．どれが random variable か?

3.1

  • 身近な例を MDP と解釈したときに，例と概念の対応関係を説明してください
  • (現実性はなくてよいので) MDP の例を1つ作成してください．dynamics に誤解の余地がないよう厳密に．(作成後に Example. 3.3 と比較して足りないものがないか，検討する)
  • Markov property が成り立つ例と成り立たない例を説明せよ
  • 将棋は MDP でしょうか? 対応関係と理由を説明してください
  • agent と environment の boundary は，どのように考えれば良いか?
  • Example 3.3 の例を説明せよ．とくに，グラフの各要素 (e.g., 白いノード，黒い小さなノード) はどのような意味か．この例は，現実にありそうかなさそうか．

3.2

  • immediate reward と cumulative reward の共通点と違いを，例をあげて説明せよ

3.3

  • return と reward の違いは? (要暗記)

3.5

  • policy とはどう定義されるか，policy の具体例をなるべく似ていない2つあげてみよう
  • value function は直感的にはなにを表しているか
  • 式 (3.12) の記法 $v_\pi(s)$ について， $v(s)$ ではなく添え字 $\pi$ がついている理由は?
  • Bellman equation とはどの式か?
    • 式中の value of a state と values of its successor states とは何か?
  • p. 59 backup diagram を説明せよ
  • Example 3.5 問題設定と，Fig. 3.2 の数字の意味を説明せよ
  • Example 3.6 問題設定を説明せよ
    • Fig. 3.3 図の意味を説明せよ．とくに，$-2$ や $-3$ の面積は下の図の方が広いのに，$-1$ の面積は上の図の方が広い理由は?

3.6

  • 2つのpolicy の良さはどのように定義されているか? 関連: どの2つのpolicyでもどちらが良いか決められるのか?
  • Bellman optimality equation とはどの式か?
  • 記法 $v_*(s)$ について， $v(s)$ ではなく， 3.4とは別の添え字 アスタリスク がついている理由は?
  • Fig. 3.4 backup diagram を説明せよ

Chapter 4

用語: dynamic programming, a finite number of

4.1

  • section titleである policy evaluation とは，何か?
    • 何ができたら policy evaluation が完了したと言えるか．
    • policy evaluation を行うためには，なにが必要か?
    • (prediction) とあるが，どのあたりが prediction か
  • two arrays と in place を使う実装で，具体的に何が違うか
    • in place 版では順序がなぜ重要か，差が大きそうな印象的な例を1つ示せ．

      the order in which states have their values updated during the sweep has a significant influence on the rate of convergence

  • 囲み内のアルゴリズムについて
    • two arrays と in place のどちらの版か?
    • 最終行 until を評価する時点での，デルタの値の意味を説明せよ

4.2

  • better policy とは，数学的にはどのように説明されているか?
  • section titleである policy improvement とは，何か?
    • 何ができたら policy improvement が完了したと言えるか．
    • policy improvement を行うためには，なにが必要か?
  • Fig. 4.1 を説明せよ
    • $k$ は何か
    • 中央列，数字の意味は?
    • 右列，矢印の意味は?
    • caption 末尾の文の意味と，この文を著者がわざわざ述べた理由として合理的な予想を説明せよ

      The last policy is guaranteed only to be an improvement over the random policy, but in this case it, and all policies after the third iteration, are optimal.

  • 式 (4.7) の不等号の左の項 $q_\pi(s,\pi’(s))$ 内の2つめの要素 $\pi’(s)$ の「型」は?
    (今までは $\pi(\cdot|s)$ は確率分布だったが…)
  • policy improvement theorem とはどのような定理か?

4.3

  • Fig. 4.2 のポリシーは，具体的にどの状態でどう行動をするか，説明せよ
  • Example 4.3
    • 問題設定と，常識的な戦略を説明せよ
    • Fig. 4.3上 で sweep 1 の線の「段」が，$50, 75, \ldots$ と $50$ 以上にあり，$25$ にはない理由を予想せよ
    • Fig. 4.3下 の不思議な形の意味を予想せよ．以下の本文との対応は?

      This policy is optimal, but not unique

4.4

  • Value iteration は，何を計算するものか?
  • Value iteration と policy iteration との関係は?
    • 2つのアルゴリズムを比較して，p. 82-83 の以下の説明との対応を確認せよ

    policy evaluation is stopped after just one sweep (one update of each state).

4.5

  • Asynchronous / synchronous という単語のの情報系の分野での典型的な使用例を説明し， Asynchronous DP との共通点を検討せよ

4.6

  • PI と GPI の差を，図で説明せよ

4.8

  • bootstrap の意味を説明せよ

Chapter 5

概念: on-policy, off-policy, target policy, behavior policy, importance sampling, biased
用語: converges asymptotically to zero

5.1

  • Example 5.1: with replacement の日本語の意味は? (ヒント: sample with/without replacement で成句)

    cards are dealt from an infinite deck (i.e., with replacement)

  • Fig. 5.1 4つのグラフの意味を説明せよ．なぜ左上が特に「がたがた」か?
  • Example 5.2 なにを計算したいのか，説明せよ

5.2

  • problem of maintaining exploration とはここではどのような意味か?

5.4

  • on-policy と off-policy は何が異なるか?
  • Consider a new environment と突然あたらしい環境を考えはじめた．この目的は何か，著者が全体として説明したい内容との関係で説明してほしい．
  • 式 (5.2) から次の式の変形を説明せよ．関連して，次の文章は，数式のどこを指すか示せ

    the sum is a weighted average with nonnegative weights summing to 1

5.5

  • importance sampling は 強化学習以外でも使われる．どのような手法か簡単な例で説明せよ．

5.7

  • Off-policy MC control の擬似コードで， $A_t \neq \pi(S_t)$ なら exit innner Loop している．exit して良い理由を説明せよ

Chapter 6

概念: temporal-difference, TD error 用語: bias

6.1

  • 式 (6.2)と 式 (6.3, 6.4), DPとの関係がどのように説明されているか確認せよ
  • 式 (6.4) のあたり，TD は samples the expected value in (6.4) と書かれているが，sample により，何を何に置き換えたか明示せよ
  • 式 (6.6) のあたり，Monte Carlo error can be written as a sum of TD errors とあるが，どれがMonte Carlo errorで，どれがsum of TD errors?
  • Fig. 6.1 具体例と，状態 $s$ やvalue function $V(s)$ との対応を説明せよ．

6.2

  • 2段落目 experimental actions と less susceptible はどのような意味か

6.3

  • Example 6.4 V(A) の推定に関して，two reasonable answers があるという．それぞれの内容を説明し，違いが生ずる理由の根本は何か検討せよ．

6.4

  • Sarsaの更新式 (6.7) とDPの関係を検討せよ

6.5-6.6

  • Q学習の更新式 (6.8) とDPの関係を検討せよ
  • Q学習は off-policy と説明されている．一方，5章で紹介されていた off-policy の手法は importance sampling を用いていた．Q学習に，importance samplingは不要なのか説明せよ．
  • 式 (6.7-6.9) に共通する内容と差異を説明せよ
  • Example 6.6 Cliff walking
    • 環境を説明せよ
    • 下のグラフからは，Sarsa がQ-learning より成績がよく見える．(1) なぜか? (2) Sarsa の方が優れた学習手法であると言う意味か?

6.7

  • maximization bias とはどのような概念か.
  • Fig 6.5 の環境とエージェントの典型的な行動を説明せよ

Chapter 7

概念: n-step return
用語: control variate

  • error reduction property の期待値 $\E_\pi$ について，具体的に計算するとしたら必要となる確率について確認せよ． つまり，$\pi(s|a)$ だけで十分だろうか?
  • Sarsa や expected Sarsa はスムーズに n-step の拡張版が紹介されたのに，n-step Q 学習がすぐ登場しない理由はなぜだろうか?