論文の概要: 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)を適用することにより、スロー状態の「凍結」という考え方に基づく近似動的プログラミングアルゴリズムフレームワークを提案する。
また,この手法を機能ベースの線形アーキテクチャを用いた関数近似設定にも拡張した。
理論的には、凍結状態アプローチの各変種によって引き起こされた後悔を分析する。
最後に、凍結状態アプローチが計算コストのごく一部を使って効果的な政策を生成するという実証的な証拠を与える一方で、決定モデルから遅い状態を単純に省略することは、しばしば実現可能なヒューリスティックではないことを示す。
関連論文リスト
- 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) - SMDP-Based Dynamic Batching for Efficient Inference on GPU-Based
Platforms [14.42787221783853]
本稿では、効率とレイテンシのバランスをとる動的グラフィックポリシーを提供することを目的とする。
提案されたソリューションは、消費電力とレイテンシのバランスをとる上で、顕著な柔軟性がある。
論文 参考訳（メタデータ） (2023-01-30T13:19:16Z) - 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) - Acting in Delayed Environments with Non-Stationary Markov Policies [57.52103323209643]
本稿では,MDPにおける学習と計画のためのフレームワークについて紹介する。
実行が遅れると、元の状態空間における決定論的マルコフポリシーは最大報酬を得るのに十分であるが、非定常である必要があることを証明します。
我々は、状態拡張に頼らずに遅延実行タスクを解く非定常Q学習スタイルのモデルベースアルゴリズムを考案した。
論文 参考訳（メタデータ） (2021-01-28T13:35:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。