めもめも

このブログに記載の内容は個人の見解であり、必ずしも所属組織の立場、戦略、意見を代表するものではありません。

GPUベースの量子回路シミュレーターについて

TL;DR;

本物の量子デバイスが手に入らない場合でも、20〜30qubit 程度の量子回路であれば、GPUベースのシミュレーターで(現実的な計算速度で)量子計算を実行することができます。物理デバイスと異なり、外部ノイズの影響を受けないため、純粋にアルゴリズムの検証にフォーカスすることができます。(意図通りの結果が得られなかった際に、ハードウェアの問題かどうかを切り分ける必要がありません。)

必要なもの

Cirq : Google が開発中の量子デバイスで実行可能な量子回路を記述するための Python library
github.com

Qulacs : GPU ベースの高速な量子回路シミュレーター
github.com

cirq-qulacs : Cirq のバックエンドに Qulacs を用いて、Cirq で記述した量子回路を高速シミュレーションするためのパッケージ
github.com

「ITエンジニアのための強化学習理論入門」的な何かのアイデア

元ネタ
incompleteideas.net

ポイント
・学習の過程がステップバイステップで理解できる(目で見える)サンプルを示すことで、「なぜそれでうまく学習できるのか」を理解することを目標とする。
・アルゴリズムを愚直に実装したコードを示すことで、数式ではなく、コードを通してアルゴリズムを理解する。

Tabular method

Multi-arm bandit による導入

MDPの枠組みは一旦無視して、強化学習のポイントとなる「考え方」を理解する

・Exploitation - Exploration のバランスが必要。典型的には ε - greedy を利用する。
・環境から収集したデータを元に、行動の価値を見積もる価値関数を構成する。
・データ収取と並行して、価値関数を逐次更新する。
・逐次更新の方法は、一義的に決まるものではないが、「差分を一定の重みで加えて修正する」という考え方が基本。
・価値の初期値を高めにセットして、初期の Exploration を促進する話も入れる。(後々、SARSA, Q-Learning でも必要になるテクニックなので。)

github.com

MDPとDynamic Programmingによる厳密解

環境のモデルがあれば、(計算量を無視すれば)DP で価値関数の厳密解が得られる(強化学習は完全に解ける)事を理解する。

・MDPの枠組みを説明。簡単な例で、状態遷移のツリーが展開される様子を理解する。
・ある状態から、すべてのツリーを網羅的に辿って、それぞれの「確率×総報酬」の和で価値関数が計算される。
・価値関数は、ポリシーごとに決まる点に注意。複数のポリシーは、それぞれの価値関数を比較することで、どちらがより優れたポリシーかが決定される。
・Bellman 方程式に変形して、Iterative に価値関数を計算する手法を説明

github.com

・「なぜこれでうまくいか」をどう説明するか???ツリーの末端から上に向かって、順次、情報が更新される様子を図解???

ポリシーアップデート

・あるポリシーの価値関数を用いて、Greedy policy を構成すると、元のポリシーよりも優れたものが得られる。
・価値関数の計算と、それを用いた Greedy policy の再構成を繰り返すことで、ベストなポリシーが得られる。

github.com

Policy iteration と Value iteration

・価値関数の計算、Greedy policy の再計算、それぞれの計算量を考えて、現実的には、計算量を削減する工夫が必要になる点を理解。
・Policy iteration において、コーディング上の工夫をする。

github.com

・価値関数の収束を待たずに、Policy を随時更新する手法として、Value iteration を説明。

github.com

Monte Carlo Method

・環境モデルがない場合、実環境から収集した断片的なデータから学習する必要がある。
・多数のエピソードを収集して、それぞれのエピソードで得られた総報酬の平均値として、価値関数を見積もる。(ただし、その後で Greedy policy を構成する上では、Action - Value function を見積もった方がよい。)
・ポリシーを固定すると Exploration できないので、「価値関数を計算するべきポリシー」とは、異なるポリシーで収集したデータを活用する手法が必要。
・一般論としては、Importance Sampling で対応。
・「価値関数を計算するべきポリシー=Greedy policy」「データ収集用ポリシー=ε - greedy」という場合、エピソードの Tail からしか学習できないので、学習の効率が悪い点を説明。

github.com

TD Method

SARSA

・価値関数の見積もりをエピソードの総報酬で見積もるのではなく、DP と同じくステップごとに評価する。TD Error による補正を加えていく。
・MC より効率的に学習できることが経験的に分かる。
・online method として ε - greedy を用いて Policy のアップデートを行う手法が SARSA。ε - greedy に伴う不確定性が課題。

Q-Learning

・SARSA を offline 化したもの。よく考えると、ステップごとの評価であれば、Importance Sampling は不要で、TD Error を Greedy Policy に対する評価に置き換えるだけでOK
・一般論としては、SARSA より効率的。ただし、Cliff walk のように作為的に Q-Learning が不利になる例も作れる。
・offline メソッドなので、experience replay (Dyna-Q)や、exploration を促進する Behavior policy の導入(Dyna-Q+)などの工夫がやりやすい。
(TD(n) はコラム程度の言及にとどめる?)

Functional approximation

・状態数が増えると、Tabular 方式が破綻するので、Functional approx を行う。最近は、NN を利用するのが流行り。
・バッチで学習するために、offline メソッドが便利。
・「TD Error の二乗平均誤差」を誤差関数として、Backpropagation でバッチ学習する方法が考えられる。
・walk game の例で説明(環境がランダムなので、環境含めてステートにしないといけない。)
github.com

・Monte Carlo tree search のもっともシンプルな例として、1step だけ先読みする手法を実装。walk game の場合、壁に自ら激突するという単純ミスを防止できる。
・Functional approximation の場合、価値関数はどうしても不正確になるので、それを compensate するために、本番時に再度、シミュレーションでエピソードを収集して補正する、という考え方。

Reinforcement Learning 2nd Edition: Exercise Solutions (Chapter 9 - Chapter 10)

Reinforcement Learning: An Introduction (Adaptive Computation and Machine Learning series)

Reinforcement Learning: An Introduction (Adaptive Computation and Machine Learning series)

Chapter 9

Exercise 9.1

Define a feature \mathbf x as a one-hot representation of states s_i, that is, x_i(s_j) = \delta_{ij}.

Then,  v(s_i) = \mathbf w^{\rm T}\mathbf x = w_i.

Exercise 9.2

There are n+1 choices of c_{ij} (c_{ij} = 0,\cdots,n) for j=1,\cdots,k.

Exercise 9.3

n = 2,\ k=2. Hence there are (1+n)^k=9 features.

 c_{1.} = [0, 0]
 c_{2.} = [1, 0]
 c_{3.} = [0, 1]
 c_{4.} = [1, 1]
 c_{5.} = [2, 0]
 c_{6.} = [0, 2]
 c_{7.} = [1, 2]
 c_{8.} = [2, 1]
 c_{9.} = [2, 2]

Exercise 9.4

Use rectangular tiles rather than square ones.

Chapter 10

Exercise 10.1

In this problem, sophisticated policies are required to reach the terminal state. Hence, an episode never end with an (arbitrarily chosen) initial policy.

Exercise 10.2

\displaystyle {\mathbf w}_{t+1}={\mathbf w}_t + \alpha[R_{t+1}+\gamma\sum_a\pi(a\mid s_{t+1})\hat q(s_{t+1},a)-\hat q(s_t,a_t)]
\nabla \hat q(s_t,a_t,\mathbf w_{t})

Exercise 10.3

Longer episodes are less reliable to estimate the true value.

Exercise 10.4

In "Differential semi-gradient Sarsa" on p.251, replace the definition of \delta with the following one:

\displaystyle \delta \leftarrow R - \overline R + \max_a \hat q(S', a, \mathbf w) - \hat q(S, A, \mathbf w)

Exercise 10.5

\displaystyle \mathbf w_{t+1} \doteq \mathbf w_t + \alpha\delta_t\nabla \hat v(S_t,\mathbf w_t)