HN 日本語サマリー

← 一覧へ戻る
AI・機械学習

動的計画法の物語 (2022)

A Tale of Dynamic Programming (2022) (iagoleal.com)

80 pointsby Brajeshwar7 コメント

要約

この記事は、グラフの最短経路探索、ニューラルネットワークの勾配計算、文脈自由文法の解析など、一見異なる分野で利用されるアルゴリズムの根底にある「動的計画法」という統一原理を解説します。リチャード・ベルマンの「最適方策は、初期状態と初期決定が何であっても、残りの決定は最初の決定の結果として生じる状態に関して最適方策を構成しなければならない」という定義を基に、状態遷移、コスト、価値関数、そして最適化の概念を、ゲームや制御理論などの例を交えながら平易に説明しています。

全文翻訳

動的計画法の物語

グラフにおける最短経路の計算、ニューラルネットワークの学習中の勾配計算、文脈自由文法の解析など、最も広く使われているアルゴリズムのいくつかが、本質的に同じ原理の実装であると言ったらどうだろうか?それは「動的計画法」と呼ばれ、数学における単純な原理が多くの分野にわたる深遠な結論へと展開される一例である。事実、この最初の段落で、動的計画法の創始者であるリチャード・ベルマン自身の言葉を用いて、そのアイデアを要約することができる。

最適な方策は、初期状態と初期決定が何であれ、残りの決定は最初の決定の結果として生じる状態に関して最適な方策を構成するという性質を持つ。

様々な文脈で動的計画法に遭遇したにもかかわらず、それらが実際には同じものであるという「ひらめき」を得るのに時間がかかったことを認めなければならない。アルゴリズムとデータ構造を学習していた頃は、より簡単な部分を先に解いてその解を後で使うために保存することで、一部のアルゴリズムを高速化できるメモ化ベースのテクニックとして認識していた。その後、仕事では、長期スケジューリング問題のための線形計画問題を数多く解くことを主に扱っている[1]。私たちが使用する主なアルゴリズムである「確率的二重動的計画法」は、当初、アルゴリズムクラスの計画法テクニックほどには見えなかった。最終的に、モデルベースの強化学習の主要な方法の1つも動的計画法と呼ばれているが、それも他の例ほどには見えなかった。

では、何が起こっているのだろうか?皆、単にかっこいい名前だからという理由で、自分のアルゴリズムに動的計画法と名付けたのだろうか?[2] 実は、ロケットの軌道計画からTeXの単語折り返しまで、これらすべての例に適用される原則がいくつか存在する。そして、そのリストは延々と続く。https://en.wikipedia.org/wiki/Dynamic_programming#Algorithms_that_use_dynamic_programming。

数学の多くの領域への旅にご招待したい。オートマトンから最適制御、マルコフ連鎖、力学系、線形計画法、さらには計量空間までを巡る。席について、この旅を楽しんでほしい!

意思決定と状態機械について

動的計画法そのものに深く入る前に、いくつかの概念を確立する必要がある。結局のところ、問題を解決する方法を学ぶ前に、どのような問題を解決したいのかを知るのが最善だろう、右?

動機付けとして、私が本当に好きなもの、昔ながらのプラットフォーマーゲームから始めよう。架空のゲーム(明らかにイタリアの配管工に関するものではない)では、キャラクターはデフォルトで何もせず idle な状態にある。しかし、コントローラーのボタンを押すことで、プレイヤーはキャラクターに shoot、jump、walk といったいくつかの行動を指示できる。そしてもちろん、これらの各アクションは画面上の対応するアニメーションを起動する。最高のバイオハザード風に言えば、このゲームでは idle な状態でのみ shoot が可能であり、jump の後は他のアクションを行う前に idle な状態に戻る必要がある。これは、転倒後にバランスを取り戻すのにかかる時間と考えてほしい。この説明はテキストでは過度に複雑に思えるかもしれないが、幸いなことに、計算機科学部の親切な人々はすでにこれらの遷移をうまく示す図を考案している。

上記のようなモデリングは、「状態機械」または「オートマトン」(ギリシャ語が好きなら)と呼ばれるものの例である。キャラクターは4つの状態のいずれかにいる可能性があり、各状態では、その状態を遷移させる一連のアクションを選択できる。より抽象的には、オートマトンは多くの「状態」s \in \mathcal{S} のいずれかにいることができるシステムであり、各状態では「アクション」a \in \mathcal{A}(s) のセットから選択できる。アクションを取るたびに、システムは「遷移関数」に従って新しい状態に変化する。

T : (s : \mathcal{S}) \times \mathcal{A}(s) \to \mathcal{S}

残念ながら、人生は無料のランチで知られているわけではなく、一般的に、状態sでアクションaを取るたびに、ある「コスト」を支払う必要がある。これは別の関数として適切にモデル化される。

c : (s : \mathcal{S}) \times \mathcal{A}(s) \to \mathbb{R}

文脈によっては、これは例えば、経済的文脈での実際の金銭的コスト、計画のための総距離または経過時間、あるいは報酬を表す負のコストでさえあり得る。

意思決定のダイナミクス

遷移Tを繰り返すことで、システムにダイナミクスが確立される。初期状態s_0から始まり、一連のアクション{a_t}を取ることで、状態空間上の軌跡が生成される。

s

_{t+1} = T(s_t, a_t)

この観点から見ると、私たちの状態機械は「制御可能な力学系」または「決定プロセス」と呼ばれ、記憶すべきさらにクールな名前である。

状態は、アクションを選択するために知っておくべきすべてをカプセル化していると主張できる。履歴や時間ステップに関係なく。実際、他の何かが選択に影響を与える場合、一般性を失うことなく、状態が追加情報も運ぶより大きなオートマトンとしてプロセスをモデル化できる。したがって、力学系を制御することは、各状態に対して有効なアクションを選択すること、つまり関数を決定することになる。

\pi : (s : \mathcal{S}) \to \mathcal{A}(s)

文献では、これは「方策」と呼ばれ、国家の状態を制御するために行動を取る政府のアナロジーである。

状態s_0から開始し、方策\piに従うと、制御を選択する必要のない決定的な力学系が生成される。

s

_{t+1} = T(s_t, \pi(s_t))

このダイナミクスは、各時間ステップでコストc(s_t, \pi(s_t))をもたらす。これらのコストの合計として\piの総コストを定義することもできるが、追加の注意点がある。例えば、何らかの理由で資金が不足し、請求書を支払うためにローンを組んだとしよう。そのような苦境にある状況で、今日お金を返すのと来年返すのとどちらが良いだろうか?

インフレや金利のような要因により、将来のコストが名目値とは異なる実際の価値を持つ場合がある。これは、時間の経過とともにコストがどれだけ減価するかを表す、問題依存の「割引係数」\gamma \in [0, 1]を導入することを促す。特定の方策\piに従う総コストは、それに従うことで生成されるすべての適切に割引かれたコストの累積合計である。\piに関連付けられた「価値関数」v^\pi : \mathcal{S}\to \mathbb{R}を、与えられた状態から開始する総コストとして定義する。

\begin{array}{rl} v^\pi(s) = & c(s_0, \pi(s_0)) + \gamma c(s_1, \pi(s_1)) + \gamma^2 c(s_2, \pi(s_2)) + \ldots \ \textrm{where} & s_0 = s, \ & s_{t+1} = T(s_t, \pi(s_t)), \ \end{array}

実用的な解釈に加えて、割引係数\gammaは解析的な観点からも重要な役割を果たす。もし|\gamma| < 1であり、コストが一様に有界である(例えば、有限のアクション空間の場合など)ならば、v^\piを定義する級数が任意のアクションと初期状態の選択に対して収束することを保証できる。つまり、M > 0が存在すると仮定する。

\forall s \in \mathcal{S}, a \in \mathcal{A}(s),, |c(s, a)| \le M.

これは、爆発しない幾何級数によって総コストをバウンドする。

\sum\limits

_{t=0}^\infty \gamma^{t}|c(s_t, a_t)| \le \sum\limits

_{t=0}^\infty \gamma^{t} M \le \frac{M}{1 - \gamma},

したがって、価値関数が適切に定義されていることを保証する。

最適な決定

複数の可能な行動コースがあるということは、どれが最善かを問うことになる。ロボットに迷路から脱出するようにプログラムする場合、最も少ない時間で済ませたい。宇宙船を月に向かわせる場合、最も少ない燃料を使用することを保証することが重要である。バーで喧嘩する場合、最も少ない負傷で相手をノックアウトしたい。何よりも、最善の方策は、現在と将来の結果の両方を、すべての時間を考慮した最も低いコストの方策である。例えば、最初の状態でのコストが高い方策が、より有利な状態に私たちを置くため、全体的にはより良い場合がある。したがって、私たちの問題は自然に「最適方策」を検索する問題として定式化できる。

状態sから開始して、時間とともに最も低い総コストを生み出す方策を求めよ。

または数学の言葉で同等に:

\begin{array}{rl} \min\limits

_\pi v^\pi(s) = \min\limits

_{a_t} & \sum\limits

{t=0}^\infty \gamma^{t}c(s_t, a_t) \ \textrm{s.t.} & s_0 = s, \ & s{t+1} = T(s_t, a_t), \ & a_t \in \mathcal{A}(s_t). \end{array}

現時点では、これは大きく恐ろしい最適化問題のように見えるかもしれないが、実際には私たちが利用できる多くの構造を含んでいる。それは次のセクションの主題である。しかし、続ける前に、古典的な問題をこの意思決定フレームワークにどのように定式化するかについて、少し脱線して見てみよう。

例:グラフの最短経路

あなたが故郷にいて、友人の「ペルーのクスコに今、歌うラマがいる」というメッセージを受け取ったとしよう。これはあなたを信じられないと同時に好奇心をそそるので、お気に入りの自転車を選んでクスコに向かう道に乗る。残念ながら、あなたの家とクスコを結ぶ直接の自転車道はない。つまり、他の都市を経由するルートを見つける必要がある。また、ラマがいつでも歌うのをやめて、山々で草を食べるいつもの行動に戻ってしまうリスクがある。これは、可能な限り短いルートを選択するという決断を促す。

上記の記述は、グラフの最短経路を見つけることの一例である。そこでは、各都市をグラフノードとして、2つの都市間の直接ルートを、重みが距離である加重エッジとして表す。家からクスコへの移動は、これらの2つのノード間の最小総距離を持つパスを見つけることを意味する。

このグラフ記述から決定プロセスへの変換は非常に簡単である。

  • 状態: グラフのノード。
  • 状態sでのアクション: sから別のノードへのエッジ。
  • 遷移: 同じエッジ上の反対側のノード。つまり、エッジs \to s'が与えられた場合、T(s, s \to s') = s'。
  • コスト: c(s, a)はエッジaの重み、つまりそのエッジを通るのにかかる時間。

sからzへの最短経路を見つけることは、初期状態をsに設定し、zをダイナミクスの終端状態にすることと同じである。

さて、いよいよ決定問題の最適化を開始する時が来た。最も単純な考えは、すべてのアクションの空間を網羅的に検索して、最善の解を見つけようとすることだ。有限の状態とホライズンであっても、可能な候補が時間ステップとともに指数関数的に増加するため、これは法外に高価になる可能性がある。実用的な方法は、このクラスの問題が自然に別々のステージに分解されることを考慮に入れる必要がある。

私たちの方法は、動的計画法の礎石である有名な「ベルマンの最適性原理」を扱うことになる。リチャード・E・ベルマン[3]自身の言葉を借りれば、それは次のように述べられている。

最適な方策は、初期状態と初期決定が何であれ、残りの決定は最初の決定の結果として生じる状態に関して最適な方策を構成するという性質を持つ。

さて、これは何を意味するのだろうか?最適性原理が私たちを教えているのは、最適方策を計算するために、アクションを行いコストを計算する反復プロセスを再帰的な手順に変換する必要があるということだ。つまり、初期状態sでアクションaを取ると、新しい状態s' = T(s, a)に移行し、そこでは再びs'から開始する最適方策を見つけるという全く同じ問題に直面することになる。このアイデアをどのように活用できるか見てみよう。

方策\piに従ったときの総コストとして定義した価値関数v^\piを覚えているだろうか。特定の状態から開始した場合の総コストである。特定の状態sから開始した場合の総コストとして定義した「最適価値関数」v^\starを定義しよう。

\begin{array}{rl} v^\star(s) = \min\limits

_{a_t} & \sum\limits

{t=0}^\infty \gamma^{t}c(s_t, a_t) \ \textrm{s.t.} & s_0 = s, \ & s{t+1} = T(s_t, a_t), \ & a_t \in \mathcal{A}(s_t). \end{array}

上記の最適化問題で、初期状態は最初のアクションを選択するためだけにしか使用されないことに注意されたい。後続のアクションはそれに直接依存せず、その結果にのみ依存する。これは、問題を2つの部分に分解できることを意味する。初期状態のみに依存する「即時コスト」の計算と、後続のすべての状態に依存する「将来コスト」の計算だ。

\begin{array}{rl} v^\star(s) = \min\limits

_{a,a_t} & {c(s, a)} + \left( \begin{array}{rl} \min\limits

_{a_t} & \sum\limits

{t=1}^\infty \gamma^{t}c(s_t, a_t) \ \textrm{s.t.} & s_1 = s', \ & s{t+1} = T(s_t, a_t), \ & a_t \in \mathcal{A}(s_t) \end{array} \right) \ \textrm{s.t.} & s' = T(s, a), \ & a \in \mathcal{A}(s). \end{array}

ここにはすでに再帰的な構造が展開されている!まだ欠けているのは、将来コストの合計がt=1から始まることに気づき、\gammaを因数分解できることだ。l = t-1と名前を付け直すと、次のようになる。

\sum\limits

_{t=2}^\infty \gamma^{t-1}c(s_t, a_t) = \gamma \sum\limits

_{t=2}^\infty \gamma^{t-2}c(s_t, a_t) = \gamma \sum\limits

_{l=1}^\infty \gamma^{l-1}c(s_l, a_l),

そしてこれをv^\starの式に適用すると、

\begin{array}{rl} v^\star(s) = \min\limits

_{a} & c(s, a) + \gamma\left( \begin{array}{rl} \min\limits

_{a_l} & \sum\limits

{l=0}^\infty \gamma^{l}c(s_l, a_l) \ \textrm{s.t.} & s_0 = s', \ & s{l+1} = T(s_l, a_l), \ & a_l \in \mathcal{A}(s_l) \end{array} \right) \ \textrm{s.t.} & s' = T(s, a), \ & a \in \mathcal{A}(s). \end{array}

これは巨大な式だが、将来コストの式がs' = T(s, a)から開始する最適値v^\star(s')と正確に同じであることが容易にわかるはずだ。このように、最適性原理は、最適方策の値が満たさなければならない再帰方程式として数学的に表現される。

\boxed{ \begin{array}{rl} v^\star(s) = \min\limits

_{a} & c(s, a) + \gamma v^\star(s') \ \textrm{s.t.} & s' = T(s, a), \ & a \in \mathcal{A}(s). \end{array} }

これは「ベルマン方程式」と呼ばれ、すべての動的計画法はそれを解く方法から成る。さらに言えば、ベルマン方程式を決定問題の再帰的な仕様と見なし、動的計画法をそれを解くあらゆる問題固有の実装と見なすことができる。

存在、一意性、および不動点

分析をさらに深める時が来た。数学者が再帰関係(ベルマン方程式など)を見ると、すぐに次のようなことを尋ね始める。v^\starについてどのような保証があるのか?それが一意であると信頼できるか?そもそも存在するのか?確かに、私たちは数学者はこれらの質問に少し心配しすぎているように見えるかもしれないが、それには正当な理由がある。すべてがうまくいくという保証に加えて、この場合、解の存在を証明することは、それを構築する方法も教えてくれる!だから注意してほしい。次のセクションでは、これらの定理をベルマン方程式を解くためのアルゴリズムに適合させる。

再帰は不動点と深い関係があり、目的のためにどちらがより実用的であるかを使用できる。動的計画法で問題を解くために、最初のステップはベルマン方程式を「ベルマン演算子」と呼ばれる演算子\mathcal{B}: (\mathcal{S}\to \mathbb{R}) \to (\mathcal{S}\to \mathbb{R})の不動点として書くことである。それは価値関数を取り、価値関数を返し、次のように定義される。

\begin{array}{rl} (\mathcal{B}v)(s) = \min\limits

_{a} & c(s, a) + \gamma v(s') \ \textrm{s.t.} & s' = T(s, a), \ & a \in \mathcal{A}(s). \end{array}

最適価値関数v^\starは不動点である。したがって、ベルマン方程式の解の存在と一意性の問題を、\mathcal{B}の不動点を見つけることに還元する。

v^\star = \mathcal{B}v^\star.

不動点に慣れていない場合、ベルマン方程式から演算子への上記の遷移は奇妙に見えるかもしれない。したがって、直感を養うために、小さな物語を通して見てみよう。

あなたが幻想的な王国の王/女王であると想像してほしい。あなたは絶対君主であり、あなたがどのような行動を取ろうとも、あなたの臣民はそれに従うだろう。最近、王国の準備金が枯渇し始め、あなたの顧問は王国の支出を最小限に抑えるために明確な統治方針を定義するように助言した。冷酷な支配者であることに加えて、あなたは偉大な数学者であり、このブログのファンでもあるので、この時点で王国を破産から救うために何をすべきかを知っているだろう。ベルマン方程式を解くことだ。

この投稿のこの時点では、まだそれを解く方法を知らないので、あなたの幻想的な世界の利点を生かして、水晶玉を覗いてくれる魔法使いを雇い、各状況が王国に将来どれだけ費用がかかるかを教えてくれる神託として役立てることにした。神々が知る多くの儀式と呪文の後、魔法使いはあなたに輝く新しい価値関数\char"1f52e: \mathcal{S}\to \mathbb{R}を渡す。

水晶玉の助言に盲目的に従うのは賢明ではないので、それを将来を予測するためだけに使い、即時の決定を下す際には自分の判断に頼ることにした。つまり、あなたは次の最適化問題を解くことによって王国を統治する。

\begin{array}{rl} (\mathcal{B}\char"1f52e)(s) = \min\limits

_{a} & c(s, a) + \gamma \char"1f52e(s') \ \textrm{s.t.} & s' = T(s, a), \ & a \in \mathcal{A}(s). \end{array}

したがって、予測から決定へのプロセスはまさにベルマン演算子である。関数\mathcal{B}vは、vを将来の推定値として、最善のアクションを選択するコストである。

便利な定理

さて、最適な決定を見つける問題をベルマン方程式を解く問題に変換し、さらにそれを不動点を見つける問題に変換した。

\mathcal{B}v^\star = v^\star.

これが、始めた場所と同じくらい複雑(ただし、より抽象的)に思えるなら、恐れることはない!私たちは強力な解析定理を呼び出して、すべてを一度に解決できる地点に到達した。バナッハの不動点定理を見よ!

完全計量空間(M,\mathrm{d})において、距離を縮小する任意の連続関数f : M \to M:

\mathrm{d}(f(v), f(w)) \le \gamma \mathrm{d}(v, w),; \textrm{for } \gamma \in [0, 1),

は一意の不動点v^\starを持つ。

さらに、任意の初期値v_0からfを反復することでv^\starに到達できる。

\lim

_{n \to \infty} f^n(v_0) = v^\star,; \forall v_0 \in M.

この手順は線形に収束し、各反復での誤差は次のようにバウンドされる。

\mathrm{d}(v_n, v^*) \le \frac{\gamma^n}{1 - \gamma} \mathrm{d}(v_0, f(v_0)).

この定理の証明はこの投稿の範囲外である[4]。しかし、距離を縮小する写像があれば、最終的にすべての点の像が1つの点に押し込められると考えることができる。

この定理で最も重要なのは、不動点を見つけるための構成的なレシピを提供してくれることだ。私たちがしなければならないのは、不動点方程式を更新ルールとして解釈することだ。

v \gets f(v),

そして、距離が特定の許容誤差を下回るまで反復することだ。上記の記述を計算手順に変換するのは簡単である。

function fixed_point(f; v0, tol)
  v = f(v0)
  while distance(v, v0) > tol
    v0 = v
    v  = f(v)  # Update rule
  end
  return v
end
価値関数の計量空間

バナッハの不動点定理をベルマン演算子に適用するには、\mathcal{B}が縮小写像となる適切な関数空間を見つける必要がある。適切な選択肢は、状態空間上の有界連続関数 C^0_b(\mathcal{S}, \mathbb{R}) であり、距離は一様ノルムで与えられる。

\mathrm{d}(v, w) = |v - w|_\infty = \sup

_{s \in \mathcal{S}} |v(s) - w(s)|

この(完全な)計量空間において、\mathcal{B}は因子\gamma(そう、割引係数)で縮小写像であることがわかる。さらに、有限状態空間の場合、すべての関数は連続かつ有界であり、これは上記のものがこの投稿で関心のあるすべてのアルゴリズムを包含することを意味する。

投稿の主なトピックからあまり離れたくない、または数学的な細部に踏み込みたくないので、必要な証明は付録に譲ることにする。

割引係数\gamma < 1を持つ任意の決定プロセスは、ベルマン方程式を満たす一意の最適価値関数v^\starを持つ。

\begin{array}{rl} v^\star(s) = \min\limits

_{a} & c(s, a) + \gamma v^\star(s') \ \textrm{s.t.} & s' = T(s, a), \ & a \in \mathcal{A}(s). \end{array}

さらに、(一意であるとは限らない)最適方策を次のように計算できる。

\begin{array}{rl} \pi^\star(s) = \argmin\limits

_{a} & c(s, a) + \gamma v^\star(s') \ \textrm{s.t.} & s' = T(s, a), \ & a \in \mathcal{A}(s). \end{array}

これらすべては、ベルマン演算子に対するバナッハの不動点定理の適用から導かれる。

上記の成果は、私が「バズーカ定理」と呼びたいものである。なぜなら、最適価値関数(したがって最適方策)の存在と一意性を保証するだけでなく、有限状態の場合の計算方法も教えてくれるからだ。これは、次のセクションで見るように。

ベルマン方程式を解く

動的計画法はベルマン方程式を解くことから成り、有名な方程式すべてと同様に、多くの可能なアプローチがある。どれを選択するかは、問題と手元にあるハードウェアによって異なる。

ここからは、状態\mathcal{S}とアクション\mathcal{A}(s)の両方の空間が有限であると仮定する。これにより、状態空間全体を探索する網羅的な方法に焦点を当てることができる。ここでのアイデアを無限空間に一般化できる他の方法(強化学習や二重動的計画法など)もある。しかし、それは別の夜の物語である…

アルゴリズムに入る前に、それらを実装するために行う必要があるいくつかの技術的な決定について議論する価値がある。

最初に気づくべきことは、プログラミング言語で関数を表現する最も直接的な方法は計算手順である[5]が、私たちのケースでは非常に非効率的であるということだ。これは、改善のために手順を変更することが計算コストが高いためである。したがって、効率上の理由から、方策と価値関数を関数としてではなく、他のデータ構造を使用して表現することが一般的である。状態空間が有限であるため、そのような関数を正確に表現できるデータ構造は数多く存在する。一般的な選択肢は配列またはハッシュマップだが、実際には係数を格納できるものであれば何でも使用できる。以下に、これらのタイプのインメモリストレージの例を示す。

# ベクトル/配列でのストレージ
# 警告:これには、後でインデックス付けするための some method idx : States -> Int が必要です
function asarray(f :: Function)
  return [f(s) for s in States]
end

# ハッシュマップ/辞書でのストレージ
function asdictionary(f :: Function)
  return Dict(s => f(s) for s in States)
end

動的計画法と関連付けられるメモ化は、完全にこの「トリック」に依存している。しかし、これは関数の計算表現の問題にすぎず、アルゴリズム設計とは全く無関係であることを念頭に置いておくのが良い。第一級関数を持つ言語では、関数合成のみを使用して動的計画法を行うことが可能である。単に、望ましいほど速くはないだろう。

アルゴリズムでは、この表現の選択を、必要なすべてのボイラープレートを処理すると仮定される2つの不透明な型 Values{States} と Policy{States, Actions} として記述する。

もう1つ言及すべき重要なことは、プロセスとはその総コストを介してのみ対話し、その構成要素に個別に触れることはないということだ[6]。したがって、それらを変換する関数をすでに作成しておこう。

# 決定問題を対応するコスト関数に変換する。
function total_cost(p :: Process)
  return (v, s, a) -> p.cost(s, a) + p.γ * v[p.next(s, a)]
end

データ構造にアクセスしていることを示すために角括弧を使用していることに注意されたい。関数を呼び出しているのではなく。

値反復法

したがって、最初のアルゴリズムである「値反復法」に到達する。前述の議論から、ベルマン演算子を任意の入力で反復すると、最適価値関数に収束することを思い出してほしい。アルゴリズムの主なアイデアは、そこから直接得られる。ベルマン方程式を不動点を見つけるための更新ルールに変換する。

v \gets \mathcal{B}v.

したがって、任意の初期価値関数v_0から開始し、上記の更新ルールを反復することができる。バナッハの不動点定理の魔法により、これは最適値に収束する。この手順は、一様誤差| v - \mathcal{B}v |_\inftyが事前に設定された許容誤差を下回るまで繰り返される。

私たちのアルゴリズムの各反復は、選択した表現でベルマン演算子を評価することから来る。したがって、total_costを使用して記述しよう。

# 決定プロセスに対応するベルマン演算子。
# 価値関数のストレージ表現 `Values` を使用する。
function bellman_operator(prob :: Process)
  return function(v)
    Bv = Values{States}()  # 空の表現
    for s in States
      Bv[s] = minimum(a -> total_cost(prob)(v, s, a), Actions(s))
    end

    return Bv
  end
end

最後に、アルゴリズムは、不動点に収束するまでbellmanによって生成された手順を反復することから成る。その後、決定された価値関数に対する最適解として方策を計算する。値反復法という名前は、更新プロセスで価値関数のみを使用し、計算された方策は役割を果たさないためである。

function value_iteration( prob :: Process     # 決定プロセスのデータ
                        ; v0 = zeros(States)  # ウォームスタート --- より良いものがわからない場合はすべてゼロ
                        , tol)                # 停止許容誤差
  # 最適価値関数はベルマン演算子の不動点である
  v_opt  = fixed_point(bellman_operator(prob); v0, tol)

  # 最適方策は、最適価値関数を持つ総コストのアクションの選択である。
  π_opt  = Policy{States, Actions}()
  for s in States
    π[s] = argmin(a -> total_cost(p)(v_opt, s, a), Actions(s))
  end

  return π_opt, v_opt
end

上記のアルゴリズムは、不動点定理の直接的な実装から来ており、このため、線形に収束することが保証されている。各反復で、\mathrm{O}(|\mathcal{S}|\cdot|\mathcal{A}|) の操作が必要なベルマン演算子の1回の評価を行う。それにもかかわらず、各反復で、最小化手順は状態ごとに独立して行われるため、\mathcal{B}vの評価は状態に対して非常に並列化可能である。

インプレース値反復法

前述の実装によって示される並列化の機会にもかかわらず、逐次的に実装すると非常に遅く感じられる場合がある。なぜなら、それは価値関数を更新するためにすべての状態を走査するまで待つからである。別の、逐次マシンにより適したアプローチは、改善された情報を他の状態に迅速に伝播させるために、価値関数をインプレースで更新することである。トレードオフは、このアプローチがもはや多くのプロセスにわたって最適化をブロードキャストできなくなることである。

アルゴリズム的には、必要な変更は、インプレースで価値関数を計算するために不動点反復手順を書き直すことだけである。

function fixed_point_inplace!(f, v; tol)
  maxerr = Inf
  while maxerr > tol
    maxerr = 0  # 可能な限り最小のエラーから開始
    for s in States
      prev = v[s]
      v[s] = f(v)[s]
      # ||f(v) - v||_∞ のコンポーネントごとの推定
      maxerr = max(maxerr, abs(v[s] - prev))
    end
  end

  return v
end

function value_iteration_inplace!(prob, v0 = zeros(States) ; tol)
  v_opt  = fixed_point_inplace!(bellman_operator(prob), v0 ; tol)

  π_opt  = Policy{States, Actions}()
  for s in States
    π[s] = argmin(a -> total_cost(p)(v_opt, s, a), Actions(s))
  end

  return π_opt, v_opt
end

下の動画では、迷路からの脱出問題におけるインプレース値反復法の動作を見ることができる。このモデルでは、各状態はグリッドのセルであり、アクションはそのセルで取ることができる方向(壁のない隣接セル)である。目標は、可能な限り少ないステップで右下の端に到達することである。これは、一様にゼロの価値とランダムな方策から開始することによって達成される。左側には各反復での価値関数が、右側には関連する方策が表示されている。

[動画: Video]

上記の実装は、実際には同じアイデアのバリエーションにすぎない。つまり、ベルマン演算子を反復して最適価値関数に収束させることである。これに加えて、多くの微調整を行うことができるが、アルゴリズムの本質には影響しない。良いウォームスタートの選択、並列化、インプレースバージョンでの状態トラバーサル順序の変更など。最適なアプローチは問題に依存する傾向がある。

方策反復法

値反復法の1つの問題は、すべての方策計算が暗黙的であることだ。なぜなら、私たちは価値関数のみを扱うからだ。したがって、価値関数がまだ収束していないために、最適方策に到達してもアルゴリズムを反復し続ける可能性がある。このセクションでは、「方策反復法」に慣れる。これは、方策を使用して価値関数を計算し、価値関数を使用して方策を計算し、最適値に収束するまで繰り返すアルゴリズムである。そのセールスポイントは、有限ステップで直接最適方策を計算できることである。

方策評価

誰かがあなたに方策\piを与え、それ以上の情報は何も与えなかったとしよう。それに関連付けられた価値関数v^\piをどのように計算できるだろうか?1つの方法は、それがベルマン方程式に似た再帰を満たすことに気づくことだが、最小化ステップはない。

\begin{array}{rl} v^\pi(s) = & c(s, a) + \gamma v^\pi(s') \ & \quad\textrm{where}; s' = T(s, \pi(s)). \end{array}

最小化ステップなしで、この方程式を不動点問題に変換することもできる。

\begin{array}{rl} (\mathcal{B}^\pi v)(s) = & c(s, a) + \gamma v(s') \ & \quad\textrm{where}; s' = T(s, \pi(s)). \end{array}

上記は計算手順として容易に記述できる。

function policy_bellman_operator(prob :: Process, pi :: Policy)
  return function(v)
    Bv = Values{States}()  # 空の表現
    for s in States
      Bv[s] = total_cost(prob)(v, s, pi[s])
    end

    return Bv
  end
end

ここで、\mathcal{B}^\piを、各状態のアクションセットが単一のオプションに縮小された決定プロセスに対するコストと見なすことができる。したがって、以前と同じ仮定の下で、それは一意の不動点を持つことを知っている。

さらに、それを更新手順に変換するとv^\piに収束する。このようにして、方策のコストを評価するアルゴリズム、想像力に乏しく「方策評価」と呼ばれるものに到達する。

function policy_evaluation(prob :: Process
                          , π   :: Policy
                          ; v0 = zeros(States)
                          , tol)
  return fixed_point(policy_bellman_operator(prob, pi); v0, tol)
end

値反復法との類似性に注意されたい。唯一の真の違いは、不動点に渡す演算子である。最適なアクションを選択する代わりに、単に方策に従うだけである。さらに、値反復法のバリエーションに関する上記のすべての議論は、方策評価にも当てはまる。同じ効果で同じ変更を行うことができる。

方策改善

方策の値関数がわかった後、次の質問はそれをより良い方策にどのように更新するかである。つまり、この情報を使用して、最適に近づくにはどうすればよいか。

以前の議論から、ベルマン演算子\mathcal{B}を非最適価値関数に適用すると、より厳密に良い結果が得られることを思い出してほしい。したがって、それは方策の価値関数を改善できる。

(\mathcal{B}v^\pi)(s) = \min

_{a \in \mathcal{A}(s)} c(s, a) + v^\pi(T(s, a)) \le c(s, \pi(s)) + v^\pi(T(s, \pi(s))) = v^\pi(s).

価値関数\mathcal{B}v^\piは、今すぐ最善のアクションを選択し、将来のすべてのステップで\piに従うコストをエンコードする。最適化問題の解を取ることで、それから方策を得ることができる。

\begin{array}{rl} \pi'(s) = \argmin\limits

_{a} & c(s, a) + \gamma v^\pi(s') \ \textrm{s.t.} & s' = T(s, a), \ & a \in \mathcal{A}(s). \end{array}

\piが最適でない限り、上記の式はより厳密に良い方策を生成する。そこから、「方策改善」と呼ばれる手順を定義でき、これは価値関数vをvが表していたものよりも良い方策\piに変換する。

function policy_improvement(prob :: Process, v :: Values)
  π = Policy{States, Actions}()
  for s in States
    π[s] = argmin(a -> total_cost(v_π, s, a), Actions(s))
  end
  return π
end
評価と改善の交互実行

任意のランダムな方策\pi_0から開始し、方策評価と改善を交互に実行することで、方策と価値関数のシーケンスを生成する。

\pi_0 \xrightarrow{\textrm{evaluation}} v^{\pi_0} \xrightarrow{\textrm{improvement}} \pi_1 \xrightarrow{\textrm{evaluation}} v^{\pi_1} \xrightarrow{\textrm{improvement}} \ldots

価値関数は単調に減少し、方策は最適に収束するまで厳密に改善される。

このようにして、別の動的計画法アルゴリズム「方策反復法」に到達する。これは、方策\piを取り、方策評価を通じてその価値関数v^\piを見つけ、最終的に方策改善を使用してより良い方策に到達することを交互に実行することから成る。有限個の方策しか存在せず、常に厳密に改善された方策を得るため、このアルゴリズムは有限ステップで最適方策に収束することが保証されている。

function policy_iteration(prob :: Process
                         ; v0 = zeros(States)
                         , π0 = rand(Policy{States, Actions))
                         , tol)
  v  = policy_evaluation(prob,  π_0 ; v0 = v_0, tol = tol)
  π = policy_improvement(prob, v)

  while π != π0
    π0 = π
    # 前のvをウォームスタートとして使用
    v  = policy_evaluation(prob,  π ; v0 = v, tol = tol)
    π  = policy_improvement(prob, v)
  end
  return π, v
end

値反復法と同様に、方策反復法も状態をどのようにトラバースするかについて多くのバリエーションを受け入れる。上記の実装は理論に近いものであり、評価と改善の両方のステップで非常に並列化可能である。それにもかかわらず、方策反復法をアルゴリズム自体よりもアルゴリズムの原則として考え、利用可能なあらゆる問題固有の情報を考慮するようにステップを適合させることが有用である。

有限ホライズンにおける後退帰納法

これまでは、常に一般的な決定プロセスを無期限に実行してきた。しかし、より構造化されたプロセスも存在する。ここでは、問題の状態空間構造を利用してこれらのアルゴリズムをはるかに高速なものに調整できる例をさらに見ていく。このセクションでは、「有限ホライズン問題」を扱い、それらの場合、値反復法を1回の反復で収束させることができることを示す!

決定プロセスにおける状態\blacksquareは、そこで取ることができるすべてのアクションがゼロコストであり、別の状態に遷移しない場合、「終端」である。

\forall a \in \mathcal{A}(s),,c(\blacksquare, a) = 0,\text{ and }, T(\blacksquare, a) = \blacksquare.

プロセスが終端状態に到達すると、ダイナミクスは実質的に終了する。本質的に、\blacksquareに到達するまで作業があり、そこでは永遠にリラックスして何もしないことができる。したがって、その名前。また、すべてのアクションが退屈なので、矢印なしで描くのが慣例である。

任意の方策に対して、ダイナミクスが有限ステップ後に終端状態に到達することが保証されている場合、それを「有限ホライズン」と呼ぶ。この場合、基盤となる状態機械のグラフは非巡回である。つまり、任意の軌跡は、非終端状態を最大でも1回訪問する。

後退帰納法アルゴリズム

状態の巧妙なトラバーサルを使用して、動的計画法のアルゴリズムを改善できる。私たちがこれまでに見たすべてのアルゴリズムでは、各反復で状態空間をトラバースする順序について仮定はなかった。多くのものが並列で実行できることさえ気づいた。その結果、この順序から生じる保証もなかった。それにもかかわらず、インプレースアルゴリズムでは、異なる順序付けが異なる情報フローを生み出す。

有限ホライズン問題では、非巡回構造を利用して、値反復法が1回の反復で収束する最適な順序付けを取得できる!それはグラフのトポロジカルソートであり、状態に自然数ラベルを付け、sがそれに遷移できるすべての状態の前に来るようにソートすることから成る。これは難しいタスクのように思えるかもしれないが、プロセスサイズに対して線形(つまり、\mathrm{O}(|\mathcal{S}| + |\mathcal{A}|) ステップ)で計算するための標準的な方法がある。前の例のトポロジカルソートを以下に示す。

一意ではないことに注意されたい。また、最も早いインデックスが終端状態に行き、その後矢印を「逆向きに」分布していくことにも注意されたい。これが次のアルゴリズムの名前の由来である。「後退帰納法」。

後退帰納法は、状態空間をより良くトラバースするためにトポロジカルソートを使用する値反復法のバリエーションである。これはインプレースアルゴリズムと同じだが、1回の反復で正確な収束が得られる。何という改善だろう!

これにより、1回のパスで収束が得られることを帰納法で証明できる。基底ケースは終端状態である。それらのコストはゼロであり、オートマトンはそれらを離れることはない。つまり、v^\star(\blacksquare) = (\mathcal{B}v^\star)(\blacksquare) = 0である。

非終端状態sでは、帰納法により、計算された価値関数vがそれより低いインデックスの状態に対して最適であると仮定する。したがって、sからより低いインデックスの状態への遷移のみが行われるため、現在の推定値v(T(s, a))はすでに最適である。次に、ローカル代入v(s) \gets (\mathcal{B}v)(s)は適切に定義され、この状態での最適値をもたらす。

\begin{array}{rl} v(v) \gets (\mathcal{B}v)(s) = \min\limits

_{a} & c(s, a) + \gamma v(s') \ \textrm{s.t.} & s' = T(s, a)\quad \color{red}{\Longleftarrow \text{ すでに解決済み}} \ & a \in \mathcal{A}(s). \end{array}

上記の議論は、1回のパスで収束できることを証明している。さて、残っているのは、証明をアルゴリズムに配置することだけである。それは値反復法と同じように機能するが、最初に状態をソートし、1回のパスのみを実行する。

# DAG向けに調整された値反復法
function backward_induction(p :: Process)
  v  = Values{States}()
  π  = Policy{States, Actions}()

  # 終端状態から初期状態へトラバース
  for s in topological_sort(States, Actions)
    v[s], π[s] = minimize(a -> total_cost(p)(v, s, a), Actions(s))
  end

  return π, v
end

これを汎用値反復法と比較して、何が得られたかを確認することをお勧めする。1つのことは明らかである。後退帰納法は、各状態に対して値反復法と同じ操作を行うが、状態空間の1回のパスのみを必要とする。これにより、はるかに効率的になる。このフレーズを何度も繰り返していることは知っているが、それに見合うほど重要である。

もう1つのより微妙な詳細は、ダイナミクスに利用できる構造が多いため、アルゴリズムはベルマン演算子についてそれほど多くの仮定をする必要がないことだ。例えば、私たちの収束証明はバナッハの不動点定理に依存していなかった。つまり、割引係数\gammaについてはいかなる仮定も必要ないことを意味する。特に、後退帰納法は割引なしのプロセスでも機能する![7]

ステージごとの状態

有限ホライズンプロセスには、それ自体でセクションを必要とするほど一般的なインスタンスがある。それは、状態とアクションが時間とともに順次進行することから成る。この場合、固定ホライズンNステップがあり、状態空間はステップtに応じてセグメント化される。

このようなプロセスの状態空間は高度に構造化されており、特に常に非巡回である。時間を逆方向に訪れることで、それをトポロジカルにソートできる。下の図は、この種のプロセスで後退帰納法が実行されている様子を示している。

このステージごとの構造が利用可能な場合、ソートの手間を省くためにそれをアルゴリズムに組み込むことができる。

function backward_induction_in_time(p :: Process)
  v  = Values{States}()
  π  = Policy{States, Actions}()

  for t in N:1           # <-- トポロジカルソートに相当
    for s in States(t)   # <-- 非常に並列化可能
      v[s], π[s] = minimize(a -> total_cost(p)(v, s, a), Actions(s))
    end
  end

  return π, v
end

上記は、以前のアルゴリズムの単なる特殊化である。その計算コストは、前処理の必要なしに、単一の値反復パスに相当するため、正確に|\mathcal{S}|\cdot|\mathcal{A}|である。通常の逆帰納法とは異なり、内部ループでは依存関係がないため、上記は非常に並列化可能でもある。これをさらに高速化するために利用できる。

非決定性:すべてを知ることはできない

さて、少し要約する時が来た。オートマトンと制御可能なダイナミクスから旅を始め、価値関数に関する特定の再帰関係(ベルマン方程式と呼ばれる)を満たすアクションの最良のセットをどのように表現できるかを示した。次に、不動点を見つける方法を通じて、この方程式を解くためのいくつかの方法を検討した。しかし、これらすべてで際立つ詳細の1つは、システムに関する完全な情報を持っていたことだ。

現実世界では、アクションを取ることで決定的な状態になるという保証はない。一般に、システムが遷移できる可能性のある状態の無数の(おそらくすべて)が存在する。遷移関数の型を変更してこれをモデル化しよう。

T : (s : \mathcal{S}) \times \mathcal{A}(s) \to M \mathcal{S}

ここでMは型を何らかの不確実なコンテキストに変換する[8]。そのような演算子の一般的な例は次のとおりだ。

  • Mはべき集合\mathcal{P}である。この場合、遷移出力は可能なすべての後続状態を列挙し、「非決定性オートマトン」を定義する。

  • Mは集合をそれらの上の確率分布に変換する。このようにして、確率的システムが複数の可能な未来を持つことになる。ただし、前の例とは異なり、この場合、各後続状態の確率がどれくらいであるかという概念がある。

  • Mは恒等関数である。このように、M \mathcal{S}= \mathcal{S}となる。これは、決定論的なケースも非決定論的なケースに含まれることを示すために役立つ。

  • Mは他者によるアクションを表す。多くの状況(ゲームなど)では、あなた以外にも状態を変更できるアクションを取ることができる他のプレイヤーがいる。彼らのアクションも結果に影響を与えるため、遷移は関数\mathcal{A}(s) \to \mathcal{S}しか返せない。

非決定論的な遷移を処理するには、価値関数を取り、不確実な将来のすべての可能なコストを単一の実数に集約する必要がある。

\rho : (\mathcal{S}\to \mathbb{R}) \times M \mathcal{S}\to \mathbb{R}

関数\rhoは、どの不確実性コンテキストを扱っているかに依存し、いくつかの例をすぐに見ていくことになる。それを使用すると、ベルマン演算子を定義できる。

\begin{array}{rl} (\mathcal{B}v)(s) = \min\limits

_{a} & c(s, a) + \gamma \rho(v, s') \ \textrm{s.t.} & s' = T(s, a), \ & a \in \mathcal{A}(s). \end{array}

以前のものとかなり似ていると思わないか?いくつかの穏やかな条件を\rhoに課せば、付録での存在と一意性の解に関するすべての導出は、このコンテキストでも有効である。さらに、私たちのすべてのアルゴリズム(値反復法、方策反復法、後退帰納法)は、システムの総コストのみを使用した。これは依然として決定論的な関数である。したがって、それらを変更なしでこのコンテキストに適用できる。どうクールだろうか?

例:漸化式とフィボナッチ

動的計画法を学習する際に、昔ながらのフィボナッチ数を計算せずに、どのようなものになるだろうか?この例は実際には非常に単純であり、開発したすべての力を利用するのは過剰である。それにもかかわらず、計算機科学のクラスで動的計画法を学習する際に遭遇するかなり一般的な最初の例であるため、この種の問題を開発した形式の観点から見る価値がある。

漸化式は、n番目の項が前の項を通じて再帰的に定義される任意の関数\mathbb{N} \to \mathbb{R}である。

f(n) = \begin{cases} c_n, & n < k \ g(n, f(n-1), \ldots, f(n-k)), & n \ge k. \end{cases}

c_nは再帰の基底ケースに対応する定数であり、他の値f(n)は前のk項に直接依存する。

この構造を持つ有名な例は、階乗関数とフィボナッチ関数である。

\begin{align

  • \mathrm{fat}(n) &= \begin{cases} 1, & n = 0 \ n \cdot \mathrm{fat}(n-1), & n \ge 1. \end{cases} \
  • \mathrm{fib}(n) &= \begin{cases} 0, & n = 0 \ 1, & n = 1 \ \mathrm{fib}(n-1) + \mathrm{fib}(n-2), & n \ge 2. \end{cases} \
    \end{align

一般に、定義を通じて直接f(n)を評価することは指数関数的に遅くなる可能性がある。しかし、動的計画法を使用すると、nに線形な時間で計算できる。

アイデアは、ベルマン方程式がまさに漸化式であるような非決定論的な決定プロセスを定義することである。次に、最適価値関数は、評価したいNまでのすべての値に対してfに等しくなる。状態は0,...,Nの数値であり、単一のダミーアクション\blacklozengeしか存在しない。遷移については、べき集合を非決定性のソースとして使用して、インデックスの漸化式に従う。これは有限ホライズンプロセスであることに注意されたい。

T(s, \blacklozenge) = \begin{cases} \emptyset, & s < k \ {s-1, s-2, \ldots, s-k}, & s \ge k. \end{cases}

即時コストについては、最初のkステージには基底ケースc_nを使用し、他のすべてはゼロである。

c(s, \blacklozenge) = \begin{cases} c_s, & s < k \ 0, & s \ge k. \end{cases}

そして、将来のインデックスのセットを集約するには、関係g自体を使用するのにこれ以上の選択肢はない。

\rho(v, s') = g(s, { v(n) \mid n \in s' }).

このセットアップでは、このシステムのベルマン方程式は元の漸化式に非常に似ている。

v(s) = \min

_{a \in {\blacklozenge}} \begin{cases} c_s, & s < k \ g(s, v(s-1), \ldots, v(s-k)), & s \ge k. \end{cases}

アクションは1つしかないため、最小化は冗長であり、その不動点は元の漸化式を満たす。問題は有限ホライズンであるため、割引係数\gammaなしで、値反復法または後退帰納法を使用して解決できる。

例として、最初の15個のフィボナッチ数を計算してみよう。次のビデオは、値反復法のステップを示している。

[動画: Video]

ホライズンが有限であるため、後退帰納法を使用してさらに改善できる!構築したばかりのプロセスは、各ステージに1つの状態を持ち、ここではNを初期状態、0を最終状態と見なす(つまり、逆方向に進む)。したがって、後退帰納法を使用して、正確にnステップでフィボナッチ方程式を評価できる。

[動画: Video]

確率的動的計画法

優れた応用分野である動的計画法は、その誕生以来、確率性を念頭に置いてきた。現実世界は不確実性に満ちており、未来を知らないことをモデル化するのに、確率ほど良いものはないだろうか?

オートマトンを確率的にするには、遷移が状態の確率分布を返す必要がある。文献では、これらのシステムは「マルコフ決定プロセス」(略してMDP)という名前で見つけることができる。この名前は、新しい状態が現在の状態とアクションのみに依存し、プロセスの履歴には依存しないという事実から来ている。マルコフ連鎖と同様に(これらは単一アクションを持つMDPである)。このようなプロセスの一般的な直感は、アクターと環境の相互作用として捉えられる。各時間ステップで、環境は状態s(アクターには知られている)にあり、アクターは異なるアクションa \in \mathcal{A}(s)の中から選択でき、それぞれがあるコストを発生させ、それと相互作用する。このアクションは、アクターの手の届かない方法(したがって確率的/非決定的)で環境に影響を与え、状態をs' = T(s, a)に変更する。この遷移が発生する前に、不確実性をもってs'がどうなるかを推定できる。これは下の図に示されている[9]。

確率性を許容することで、さらに多くのクールな状況をモデル化できるようになる。例えば、ビデオゲームをプレイするロボットだ!状態はゲームの内部状態、またはプレイヤーが利用できるそれらの部分的な観測であり、アクションはコントローラーのボタンである。遷移はゲーム内部のものであり、コストは勝利/敗北要因に関連している。Volodymyr Mnihら[10]の「Playing Atari with Deep Reinforcement Learning」という論文を聞いたことがあるだろうか?その中で、彼らはアタリ2600ゲームをプレイできるロボットを訓練するために強化学習を使用しており、すべてのモデリングは、この段落での議論と非常に似た方法でマルコフ決定プロセスを通じて行われている。ぜひチェックすることをお勧めする。

未来を知ることはできないため、通常のツールは、可能なすべての結果を取り、それらのコストを平均することである。これにより、確率的遷移から決定論的な値を抽出するための集約関数が得られる[11]。

\rho(v, S) = \mathbb{E}[v(S)].

「確率的動的計画法」は、すべての可能な方策にわたるマルコフ決定プロセスの期待総コストを最適化することに特化した分野である。

v^\star(s) = \min

_\pi v^\pi(s) = \min

_{a_t} \mathbb{E}\left[ \sum\limits

{t=0}^\infty \gamma^{t}c(s_t, a_t) ,\middle|, s_0 = s,, s{t+1} = T(s_t, a_t) \right]

予想通り、上記はベルマン方程式に相当する。期待値は線形であるため、導出は決定論的なプロセスで行ったものと非常に似ている。

\begin{array}{rl} v^\star(s) = \min\limits

_{a} & c(s, a) + \gamma \mathbb{E}\left[v^\star(s') \right] \ \textrm{s.t.} & s' = T(s, a), \ & a \in \mathcal{A}(s). \end{array}

有限状態空間の場合、この方程式は決定論的なものと同じ収縮特性を持つ。したがって、値反復法と方策反復法のツールもMDPを解くために容易に利用できる。それらの計算複雑性は悪く、なぜなら平均を計算すると、更新ルールv \gets \mathcal{B}vが\mathrm{O}(|\mathcal{S}|^2|\cdot|\mathcal{A}|)の操作を必要とするからである。

私たちの旅の終わり

さて、ついに動的計画法の概要の終わりに到達した。あなたがそれを読むのが楽しかったのと同じくらい、私がそれを書くのが楽しかったことを心から願っている。そして、DPがあなたの問題解決ツールキットの中で当然の場所を得ることを願っている![12]

もちろん、単一のブログ投稿では、DPのような広大な主題をすべて網羅するには小さすぎる。価値関数を単に計算するのではなく推定すること、無限状態空間、連続時間、そして私たちができる多くのクールなことに関する問題がある。強化学習との多くのつながりもあり、この投稿ではその表面をかすめただけだ。残念ながら、これらは別の夜の物語として残るだろう。

さようなら、また次回!

謝辞

この投稿は、ペドロ・ザビエルとの一連の会話の後、形になった。賢い人に何かを説明することの良い点は、その過程で多くを学ぶことができることだ。時にはブログ投稿を書くのに十分なほど学ぶことさえある。

イヴァニ・イヴァノヴァにも、素晴らしいタイプミスハンターであったことに感謝している。もしタイプミスが残っているなら、それは私が怠惰だからだ…彼女は素晴らしい仕事をした。

付録(無限ホライズンでの収束)

この付録では、ベルマン演算子

\begin{array}{rl} (\mathcal{B}v)(s) = \min\limits

_{a} & c(s, a) + \gamma v(s') \ \textrm{s.t.} & s' = T(s, a), \ & a \in \mathcal{A}(s) \end{array}

を有界連続関数の空間上で「単調縮小写像」であることを示す。

まず「単調性」から証明を始める。そのためには、一様順序付けによって価値関数の空間に偏順序を導入する。

v \le w \iff \forall s \in \mathcal{S},, v(s) \le w(s).

ベルマン演算子は価値関数の順序付けを一様に保存する。

v \le w \implies \mathcal{B}v \le \mathcal{B}w.

仮説v \le wは、任意の状態sとアクションaに対して、次を意味する。

c(s, a) + \gamma v(T(s,a)) \le c(s, a) + \gamma w(T(s,a)).

これは任意のアクションaに対して有効なので、両辺の最小値を取ることで不等式が保存される。

\min

_{a \in \mathcal{A}(s)} c(s, a) + v(T(s,a)) \le \min

_{a \in \mathcal{A}(s)} c(s, a) + w(T(s, a)) \
(\mathcal{B}v)(s) \le (\mathcal{B}w)(s).

上の行はすべての状態に対して有効であり、証明を完了する。

\mathcal{B}のもう1つの重要な特性は、入力vの一様平行移動が出力も一様に平行移動することである。

任意の定数kに対して、\mathcal{B}(v + k) = \mathcal{B}v + \gamma k.

\begin{array}{rlll}
\mathcal{B}(v + k)(s) &= &\min\limits

_{a} & c(s, a) + \gamma (v(s') + k) \
&&\textrm{s.t.} & s' = T(s, a), \
&& & a \in \mathcal{A}(s) \
&=& \min\limits

_{a} & c(s, a) + \gamma v(s') + \gamma k \
&&\textrm{s.t.} & s' = T(s, a), \
&& & a \in \mathcal{A}(s).
\end{array}

項\gamma kはアクションaに依存しないため、最適化の外に出すことができる。

\mathcal{B}(v + k)(s) = \mathcal{B}(v)(s) + \gamma k.

これにより、定理が完了する。

最後に、ベルマン演算子が割引係数によって有界連続関数の空間を縮小することを示そう。

ベルマン演算子はリプシッツ定数\gamma、|\mathcal{B}v - \mathcal{B}w|\infty \le \gamma |v - w|\inftyで連続である。\gamma < 1の場合、それは縮小写像である。

一様ノルムの定義から、任意の状態sに対して、次が得られる。

v(s) - w(s) \le |v - w|\infty \
v(s) \le w(s) + |v - w|
\infty.

証明した単調性から、両辺に\mathcal{B}を適用すると、この不等式が保存される。

(\mathcal{B}v)(s) \le \mathcal{B}(w + |v - w|_\infty)(s).

右辺は一様平行移動を持つため、定数を取り出すことができる。

\begin{aligned}
(\mathcal{B}v)(s) &\le (\mathcal{B}w)(s) + \gamma |v - w|\infty \
(\mathcal{B}v)(s) - (\mathcal{B}w)(s) &\le \gamma |v - w|
\infty.
\end{aligned}

ノルムは対称的であるため、逆方向(w - vの場合)にも同様の導出を行い、絶対値の不等式を得ることができる。上限を取ると、それは私たちが望む結果になる。

\begin{aligned}
|(\mathcal{B}v)(s) - (\mathcal{B}w)(s)| &\le \gamma |v - w|_\infty \
\sup

{s\in\mathcal{S}} |(\mathcal{B}v)(s) - (\mathcal{B}w)(s)| &\le \gamma |v - w|\infty \
|\mathcal{B}v - \mathcal{B}w|\infty &\le \gamma |v - w|\infty.
\end{aligned}

最後に、バナッハの不動点定理と上記から、\gamma < 1の場合、演算子\mathcal{B}は一意の不動点を持つと結論付ける。したがって、割引係数を持つ任意の決定プロセスは解可能であり、一意の最適価値関数v^\starを持つ。


  1. より正確には、水力、火力、再生可能エネルギー源など、多くのエネルギー源の中から、特定の電力需要を供給するために、将来の不確実性を考慮して、どれを選択するかを決定する必要がある水熱 dispatch 問題を扱っています。例えば:水力は安価でクリーンだが、すべて使用すると水不足になるリスクがある。最適なエネルギーディスパッチを見つけることは、動的計画法を通じて解決される。↩︎

  2. リチャード・ベルマン自身も、かっこいい響きに基づいて命名したことを認めている。↩︎

  3. Dynamic Programming, Princeton Landmarks in Mathematics and Physics (Princeton, NJ: Princeton University Press, 1957), ch 3, p. 83.↩︎

  4. 証明の難しさからではなく、トピックからの逸脱であるため、範囲外である。解析に興味があるなら、ぜひ証明を試してみてほしい。主なアイデアは、収縮特性を使用して、fの反復間の距離がゼロに収束する必要があることを示すことだ。↩︎

  5. ほとんどのプログラミング言語では、「関数」と呼ばれている。↩︎

  6. これが、動的計画法が他の種類のベルマン方程式(例えば非加算コスト)を満たす決定プロセスにも適用できることを意味するのではないかと疑問に思うかもしれない。答えは「はい」だ!Dimitri P. Bertsekas著、『Abstract Dynamic Programming』(Belmont, Mass: Athena Scientific, 2013)は、そのための良い出発点となる。ただし、これらのケースではさらに多くの技術的な詳細に対処する必要があることに注意してほしい。↩︎

  7. 値反復法とは対照的に、コストが実数であるという仮定にも依存しない。任意の半環で十分だ。しかし、脱線しすぎた…これはこの投稿の範囲外である。↩︎

  8. 技術的な定義では、Mはモナドであるべきだ。しかし、それらの詳細を議論することはここでは範囲外である。同様の文脈でこの構造を議論するには、オートマトンとコンテキストに関するこの他の投稿を参照してほしい。↩︎

  9. Richard S. SuttonとAndrew G. Barto著、『Reinforcement Learning: An Introduction』、第2版、Adaptive Computation and Machine Learning Series(Cambridge, Massachusetts: The MIT Press, 2018)で見つかった図を緩やかに基にしている。↩︎

  10. 「Playing Atari with Deep Reinforcement Learning」、2013年12月、https://doi.org/10.48550/ARXIV.1312.5602。↩︎

  11. 平均が最も一般的な選択肢だが、唯一の選択肢ではない。多くの実生活の状況ではリスク回避が求められ、コヒーレントリスク尺度を用いた動的計画法も同様にうまく機能する。↩︎

  12. 実際、不動点と再帰全体がその場所を占めるべきだ。それらはどこにでもある!↩︎