動的計画法の物語 (2022)

もし私が、グラフの最短経路を見つけたり、ニューラルネットワークの勾配を計算したり、文脈自由文法を解析したりするために使用される最も一般的なアルゴリズムのいくつかが、本質的に同じ原理の実装であると言ったらどうでしょうか？ それは動的計画法と呼ばれ、数学における、単純な原理が多くの分野にわたる深遠な結論へと展開される一例です。 実際、この最初の段落で、動的計画法の創始者であるリチャード・ベルマン自身の言葉を使ってそのアイデアを要約できます。 「最適方策は、初期状態と初期決定が何であっても、残りの決定は最初の決定の結果として生じる状態に関して最適方策を構成しなければならない」という性質を持つ。 私は、動的計画法をさまざまな文脈で遭遇したにもかかわらず、それらが実際には同じものであるという「クリック」を最終的に得るのにしばらく時間がかかったことを認めなければなりません。 アルゴリズムとデータ構造を学習する際、それはメモ化ベースのテクニックであり、より簡単な部分を最初に解決して後で使用するために保存することで、一部のアルゴリズムを高速化できるものでした。 その後、仕事では、長期スケジューリング問題のために多くの線形計画法を解決することが主です。 私たちが使用する主なアルゴリズムである確率的二重動的計画法は、最初はアルゴリズムクラスのプログラミングテクニックほどには見えませんでした。 最後に、モデルベースの強化学習の主な方法の1つが再び動的計画法と呼ばれ、これも他のインスタンスほどには見えませんでした。 それで、何が起こっているのでしょうか？ みんな、単にかっこいい名前だからという理由で、自分のアルゴリズムを動的計画法と呼ぶことを選んだのでしょうか？ 実際には、ロケットの軌道を計画することからTeXの単語折り返しまで、これらのすべてのインスタンスに適用される原則がいくつかあります。 そしてリストは延々と続きます。 私はあなたを数学の多くの領域への旅に招待したいと思います。 オートマトンから最適制御まで、マルコフ連鎖、力学系、線形計画法、さらには計量空間を通過します。 席について、乗り心地を楽しんでください！ 意思決定と状態機械について 動的計画法そのものに入る前に、まずいくつかの概念を確立する必要があります。 結局のところ、問題を解決するための方法を学ぶ前に、どの問題を解決したいのかを知るのが一番ですよね？ 動機付けとして、私が本当に好きなものから始めましょう。昔ながらのプラットフォーマーゲームです。 私たちの架空のゲームは、明らかにイタリアの配管工についてのゲームではありませんが、キャラクターはデフォルトで何もせずにアイドル状態です。 しかし、コントローラーのボタンを押すと、プレイヤーはキャラクターにシューティング、ジャンプ、またはウォークなどのいくつかのことをコマンドできます。 そして、もちろん、これらの各アクションは画面上の対応するアニメーションをアクティブにします。 最高のバイオハザードスタイルで、このゲームはアイドル状態のときにのみキャラクターがシューティングすることを許可し、他のアクションを実行する前にジャンプ後にアイドル状態にする必要があります。 それを、バランスを回復するのにかかる時間と考えてください。 この説明はテキストでは過度に複雑に見えるかもしれませんが、幸いなことに、コンピュータサイエンス学科の素晴らしい人々は、これらの遷移をうまく示す図をすでに発明しています。 ブラウザはSVGをサポートしていません。 上記のモデリングは、状態機械またはオートマトン（ギリシャ語が好きなら）と呼ばれるもののインスタンスです。 キャラクターがなりうる4つの状態があり、それぞれで実行できるアクションのセットがあり、状態を遷移させます。 より抽象的には、オートマトンは多くの状態 s ∈ S のいずれかにあるシステムであり、各状態では、アクションのセット a ∈ A(s) から選択できます。 アクションを実行すると、システムは遷移関数 T : (s : S) × A(s) → S に従って新しい状態に変化します。 残念ながら、人生は無料のランチで知られておらず、一般的に、状態 s でアクション a を取るときは、別の関数 c : (s : S) × A(s) → ℝ として適切にモデル化された特定のコストを支払う必要があります。 文脈によっては、これは、例えば、経済的文脈での実際の金銭的コスト、計画のための総距離または経過時間、あるいは報酬を表す負のコストでさえあります。 意思決定の力学 遷移 T を反復することで、システムに力学が生まれます。 初期状態 s₀ から開始し、一連のアクション {aₜ} を取ることで、状態空間を横断する軌道を生成します。 sₜ₊₁ = T(sₜ, aₜ)。 この観点から見ると、私たちの状態機械は制御可能な力学系または意思決定プロセスと呼ばれ、さらにいくつかのクールな名前を覚えることができます。 状態は、以前の履歴や時間ステップに関係なく、アクションを選択するために知っておく必要があるすべてをカプセル化していると主張できます。 実際、他の何かがあなたの選択に影響を与える場合、一般性を失うことなく、状態に追加情報も運ぶようにプロセスをより大きなオートマトンとしてモデル化できます。 したがって、力学系を制御することは、各状態に対して有効なアクションを選択すること、つまり関数 π : (s : S) → A(s) を選択することになります。 文献では、これは政府が国の状態を制御するために行動を取ることにちなんで、ポリシーと呼ばれます。 状態 s₀ から開始し、ポリシー π に従うと、制御を選択する必要のない決定論的な力学系が生成されます。 sₜ₊₁ = T(sₜ, π(sₜ))。 この力学系は、各時間ステップでコスト c(sₜ, π(sₜ)) を生成します。 π の総コストをそれらのコストの合計として定義できますが、追加の詳細に注意する必要があります。 たとえば、何らかの理由で、お金が不足していて、請求書を支払うためにローンを組んだとします。 これらの苦しい状況で、今日お金を返すのと来年返すのとどちらを好みますか？ インフレや金利などの要因により、将来のコストが名目値とは異なる実際の価値を持つ場合があります。 これにより、問題に依存する割引係数 γ ∈ [0, 1] を導入することになります。これは、時間の経過とともにコストがどれだけ減価するかを表します。 特定のポリシー π に従う総コストは、それに従うことによって生成されるすべての適切に割引されたコストの累積合計です。 π に関連付けられた価値関数 v^π : S → ℝ を、与えられた状態から開始する総コストとして定義します。 v^π(s) = c(s₀, π(s₀)) + γ c(s₁, π(s₁)) + γ² c(s₂, π(s₂)) + … ここで s₀ = s、 sₜ₊₁ = T(sₜ, π(sₜ))、 初期状態からの開始コストの実際の解釈に加えて、割引係数 γ は分析的な観点からも重要な役割を果たします。 もし |γ| < 1 で、コストが一様に制限されている場合（たとえば、有限のアクション空間の場合）、任意の選択されたアクションと初期状態に対して v^π を定義する級数が収束することを保証できます。 つまり、M > 0 が存在し、∀ s ∈ S, a ∈ A(s) で |c(s, a)| ≤ M と仮定します。 これは、爆発しない幾何級数によって総コストを制限します。 ∑_{t=0}^∞ γᵗ|c(sₜ, aₜ)| ≤ ∑_{t=0}^∞ γᵗ M ≤ M / (1 - γ)、 これにより、価値関数が適切に定義されていることが保証されます。 最適な決定 複数の可能な行動コースがあるということは、どれが最善かを尋ねることを促します。 ロボットに迷路から脱出するようにプログラムする場合、最も短い時間を取りたいと思います。 宇宙船を月に制御する場合、最も少ない燃料を使用することを保証することが重要です。 バーで殴り合う場合、最も少ない怪我を負いながら敵をノックアウトしたいと思うでしょう。 何よりも、最善のポリシーは、現在と将来の結果の両方を含む、すべての時間を考慮した最もコストの低いポリシーです。 たとえば、最初の状態でのコストが高いポリシーが、より有利な状態に私たちを置くため、全体としてはより良い場合があります。 したがって、私たちの問題は、自然に検索として定式化されます。