論文の概要: Faster Approximate Dynamic Programming by Freezing Slow States
- arxiv url: http://arxiv.org/abs/2301.00922v1
- Date: Tue, 3 Jan 2023 01:35:24 GMT
- ステータス: 翻訳完了
- システム内更新日: 2023-01-04 14:11:28.518328
- Title: Faster Approximate Dynamic Programming by Freezing Slow States
- Title（参考訳）: スロー状態凍結による高速近似動的プログラミング
- Authors: Yijia Wang, Daniel R. Jiang
- Abstract要約: 高速低速構造を持つ無限水平マルコフ決定過程(MDP)を考察する。
このような構造は、シーケンシャルな決定を高周波で行う必要がある実世界の問題では一般的である。
本稿では、遅い状態の「凍結」という概念に基づく近似動的プログラミングフレームワークを提案する。
- 参考スコア（独自算出の注目度）: 5.6928413790238865
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider infinite horizon Markov decision processes (MDPs) with fast-slow
structure, meaning that certain parts of the state space move "fast" (and in a
sense, are more influential) while other parts transition more "slowly." Such
structure is common in real-world problems where sequential decisions need to
be made at high frequencies, yet information that varies at a slower timescale
also influences the optimal policy. Examples include: (1) service allocation
for a multi-class queue with (slowly varying) stochastic costs, (2) a restless
multi-armed bandit with an environmental state, and (3) energy demand response,
where both day-ahead and real-time prices play a role in the firm's revenue.
Models that fully capture these problems often result in MDPs with large state
spaces and large effective time horizons (due to frequent decisions), rendering
them computationally intractable. We propose an approximate dynamic programming
algorithmic framework based on the idea of "freezing" the slow states, solving
a set of simpler finite-horizon MDPs (the lower-level MDPs), and applying value
iteration (VI) to an auxiliary MDP that transitions on a slower timescale (the
upper-level MDP). We also extend the technique to a function approximation
setting, where a feature-based linear architecture is used. On the theoretical
side, we analyze the regret incurred by each variant of our frozen-state
approach. Finally, we give empirical evidence that the frozen-state approach
generates effective policies using just a fraction of the computational cost,
while illustrating that simply omitting slow states from the decision modeling
is often not a viable heuristic.
- Abstract（参考訳）: 高速な構造を持つ無限地平面マルコフ決定過程(MDPs)を考えると、状態空間の特定の部分がより速く(そしてある意味ではより影響力のある)移動し、他の部分はより緩やかに遷移する。
このような構造は、高頻度でシーケンシャルな決定を行う必要がある実世界の問題では一般的であるが、より遅い時間スケールで異なる情報が最適ポリシーに影響を与える。
例えば、(1)確率的コストの低い(ゆっくりと変化する)マルチクラスキューのサービス割り当て、(2)環境状態のレスレスマルチアームバンディット、(3)日頭とリアルタイムの両方の価格が会社の収益に寄与するエネルギー需要応答などである。
これらの問題を完全に捉えたモデルは、しばしば大きな状態空間と(頻繁な決定のため)大きな有効時間水平線を持つMDPとなり、計算的に難解になる。
より単純な有限水平MDP(下層MDP)の集合を解き、より遅い時間スケール(上層MDP)で遷移する補助MDPに値反復(VI)を適用することにより、スロー状態の「凍結」という考え方に基づく近似動的プログラミングアルゴリズムフレームワークを提案する。
また,この手法を機能ベースの線形アーキテクチャを用いた関数近似設定にも拡張した。
理論的には、凍結状態アプローチの各変種によって引き起こされた後悔を分析する。
最後に、凍結状態アプローチが計算コストのごく一部を使って効果的な政策を生成するという実証的な証拠を与える一方で、決定モデルから遅い状態を単純に省略することは、しばしば実現可能なヒューリスティックではないことを示す。
関連論文リスト
- OP-LoRA: The Blessing of Dimensionality [93.08208871549557]
低ランクアダプタは、少数のパラメータしか持たない大型モデルの微調整を可能にする。
しばしば最適化の課題を提起するが、収束性は低い。
推論コストを増大させることなく、トレーニングを加速する過剰パラメータ化アプローチを導入する。
視覚言語タスクの改善、特に画像生成の顕著な向上を実現している。
論文 参考訳（メタデータ） (2024-12-13T18:55:19Z) - Understanding Warmup-Stable-Decay Learning Rates: A River Valley Loss Landscape Perspective [66.80315289020487]
Warmup-Stable-Decay (WSD) スケジュールは、一定の学習率を使用して、所定の計算予算なしで無限に継続できるイテレーションのメインブランチを生成する。
プレトレーニング損失は,河底に川がある深い谷に類似した河谷景観を呈することを示す。
この理論にインスパイアされたWSD-Sは、従来のチェックポイントの崩壊フェーズを再利用し、メインブランチを1つだけ保持するWSDの変種である。
論文 参考訳（メタデータ） (2024-10-07T16:49:39Z) - Accelerating Dissipative State Preparation with Adaptive Open Quantum Dynamics [0.0]
様々な散発的な状態準備スキームは、基本的な時間的絡み合いのトレードオフに悩まされている。
我々は、このトレードオフを完全に回避するために、最小限の適応力学を使用する方法を示す。
論文 参考訳（メタデータ） (2024-09-09T19:11:07Z) - Temporal Feature Matters: A Framework for Diffusion Model Quantization [105.3033493564844]
拡散モデルはマルチラウンド・デノナイジングの時間ステップに依存している。
3つの戦略を含む新しい量子化フレームワークを導入する。
このフレームワークは時間情報のほとんどを保存し、高品質なエンドツーエンド生成を保証する。
論文 参考訳（メタデータ） (2024-07-28T17:46:15Z) - A physics-informed neural network method for the approximation of slow invariant manifolds for the general class of stiff systems of ODEs [0.0]
我々は、遅い不変多様体(SIM)の発見のための物理インフォームドニューラルネットワーク(PINN)アプローチを提案する。
削減順序のブラックボックスサロゲートモデルを構成する他の機械学習(ML)アプローチとは対照的に,我々のアプローチはベクトル場を高速かつ低速なコンポーネントに分解する。
提案手法は,QSSA,PEA,CSPが提供する手法よりも,同等あるいは高い精度でSIM近似を提供することを示す。
論文 参考訳（メタデータ） (2024-03-18T09:10:39Z) - Fast, Scalable, Warm-Start Semidefinite Programming with Spectral
Bundling and Sketching [53.91395791840179]
我々は、大規模なSDPを解くための、証明可能な正確で高速でスケーラブルなアルゴリズムであるUnified Spectral Bundling with Sketching (USBS)を提案する。
USBSは、20億以上の決定変数を持つインスタンス上で、最先端のスケーラブルなSDP解決器よりも500倍のスピードアップを提供する。
論文 参考訳（メタデータ） (2023-12-19T02:27:22Z) - StreamFlow: Streamlined Multi-Frame Optical Flow Estimation for Video
Sequences [31.210626775505407]
連続するフレーム間のオクルージョンは、長い間、光学的フロー推定において重要な課題を提起してきた。
本稿では,ビデオ入力に適したストリーム・イン・バッチ・マルチフレーム(SIM)パイプラインを提案する。
StreamFlowは、挑戦的なKITTIとSintelデータセットのパフォーマンスだけでなく、排他的領域でも特に改善されている。
論文 参考訳（メタデータ） (2023-11-28T07:53:51Z) - TFMQ-DM: Temporal Feature Maintenance Quantization for Diffusion Models [52.454274602380124]
拡散モデルは非常に時間ステップ$t$に大きく依存し、良好なマルチラウンドデノジングを実現している。
本稿では,時間情報ブロック上に構築した時間的特徴保守量子化(TFMQ)フレームワークを提案する。
先駆的なブロック設計により、時間情報認識再構成(TIAR)と有限集合キャリブレーション(FSC)を考案し、完全な時間的特徴を整列させる。
論文 参考訳（メタデータ） (2023-11-27T12:59:52Z) - Non-stationary Reinforcement Learning under General Function
Approximation [60.430936031067006]
まず,非定常MDPに対する動的ベルマンエルダー次元(DBE)と呼ばれる新しい複雑性指標を提案する。
提案する複雑性指標に基づいて,SW-OPEAと呼ばれる新しい信頼度セットに基づくモデルフリーアルゴリズムを提案する。
SW-OPEAは,変動予算がそれほど大きくない限り,有効に有効であることを示す。
論文 参考訳（メタデータ） (2023-06-01T16:19:37Z) - Initial-state-dependent quantum speed limit for dissipative state
preparation: Framework and optimization [6.211723927647019]
我々は、エネルギー固有状態の1つであるマルコフ散逸状態準備スキームに焦点をあてる。
我々は、実際の進化時間のより洗練された測定値を提供する初期状態依存量子速度制限(QSL)を導出する。
本稿では,ベル状態作成のための散逸型Rydberg原子系において,我々の戦略の有効性を実証する。
論文 参考訳（メタデータ） (2023-03-23T00:19:32Z) - Intermittently Observable Markov Decision Processes [17.75610745277615]
本稿では,制御者が信頼できない通信チャネルを通じてプロセスの状態情報を知覚するシナリオについて考察する。
地平線全体にわたる状態情報の伝達はベルヌーイ損失過程としてモデル化される。
木MDPに対する2つの有限状態近似を開発し,その近似を効率的に求める。
論文 参考訳（メタデータ） (2023-02-23T03:38:03Z) - Toward Efficient Gradient-Based Value Estimation [4.365720395124051]
強化学習における値推定の勾配に基づく手法は、時間差(TD)学習法よりも典型的にはるかに遅い。
この速度の根本原因について検討し,メアン・スクエア・ベルマン・エラー(MSBE)がヘッセンの条件数が大きいという意味で不条件損失関数であることを示す。
本稿では,ガウス・ニュートン方向をほぼ追従し,パラメータ化に頑健な,低複雑性なバッチフリー近似法を提案する。
RANSと呼ばれる本アルゴリズムは, ほぼ同一でありながら, 残留勾配法よりもかなり高速であるという意味で, 効率的である。
論文 参考訳（メタデータ） (2023-01-31T16:45:49Z) - SMDP-Based Dynamic Batching for Efficient Inference on GPU-Based
Platforms [14.42787221783853]
本稿では、効率とレイテンシのバランスをとる動的グラフィックポリシーを提供することを目的とする。
提案されたソリューションは、消費電力とレイテンシのバランスをとる上で、顕著な柔軟性がある。
論文 参考訳（メタデータ） (2023-01-30T13:19:16Z) - Shortcuts to adiabatic population inversion via time-rescaling:
stability and thermodynamic cost [0.0]
本研究では,2レベル量子系の集団反転を高速化する問題について検討する。
制御パラメータの系統的誤差に対する力学の忠実さは、他のSTAスキームと同等であることが示されている。
論文 参考訳（メタデータ） (2022-04-29T20:27:02Z) - Collaborative Intelligent Reflecting Surface Networks with Multi-Agent
Reinforcement Learning [63.83425382922157]
インテリジェント・リフレクション・サーフェス(IRS)は将来の無線ネットワークに広く応用されることが想定されている。
本稿では,エネルギー収穫能力を備えた協調型IRSデバイスを用いたマルチユーザ通信システムについて検討する。
論文 参考訳（メタデータ） (2022-03-26T20:37:14Z) - An Adaptive State Aggregation Algorithm for Markov Decision Processes [10.494611365482028]
同様のコスト・ツー・ゴー値の状態を動的にグループ化することで、価値反復更新のコストを削減できるMDPを解くための直感的なアルゴリズムを提案する。
我々のアルゴリズムはほぼ確実に(2varepsilon / (1 - gamma) に収束し、(γ) は割引係数であり、集約された状態は最大で (varepsilon) 異なる。
論文 参考訳（メタデータ） (2021-07-23T07:19:43Z) - A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs [117.82903457289584]
有限水平マルコフ決定過程(MDPs)における新たな問題依存的下界を導出する。
我々の下界は一般の場合よりもかなり小さく、最小の作用ギャップでスケールしないことが示される。
この最後の結果($poly(H)$の条件で、$H$は地平線である)は、楽観的なアルゴリズムのポリシーギャップに基づいて、後悔の意を表すことによって達成可能であることを示す。
論文 参考訳（メタデータ） (2021-06-24T13:46:09Z) - Acting in Delayed Environments with Non-Stationary Markov Policies [57.52103323209643]
本稿では,MDPにおける学習と計画のためのフレームワークについて紹介する。
実行が遅れると、元の状態空間における決定論的マルコフポリシーは最大報酬を得るのに十分であるが、非定常である必要があることを証明します。
我々は、状態拡張に頼らずに遅延実行タスクを解く非定常Q学習スタイルのモデルベースアルゴリズムを考案した。
論文 参考訳（メタデータ） (2021-01-28T13:35:37Z) - Balancing Rates and Variance via Adaptive Batch-Size for Stochastic
Optimization Problems [120.21685755278509]
本研究は,ステップサイズの減衰が正確な収束に必要であるという事実と,一定のステップサイズがエラーまでの時間でより速く学習するという事実のバランスをとることを目的とする。
ステップサイズのミニバッチを最初から修正するのではなく,パラメータを適応的に進化させることを提案する。
論文 参考訳（メタデータ） (2020-07-02T16:02:02Z) - Dynamic of Stochastic Gradient Descent with State-Dependent Noise [84.64013284862733]
勾配降下(SGD)とその変種は、ディープニューラルネットワークを訓練するための主流の方法である。
局所ミニマの局所領域におけるSGDのノイズの共分散は状態の二次関数であることを示す。
本稿では,SGDのダイナミクスを近似するために,状態依存拡散を伴う新しいパワーローダイナミクスを提案する。
論文 参考訳（メタデータ） (2020-06-24T13:34:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。