論文の概要: Online Resource Allocation with an Endogenous Markov State: Fewer LP Solves Earn More
- arxiv url: http://arxiv.org/abs/2610.09577v1
- Date: Wed, 07 Oct 2026 07:21:03 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-08 21:58:22.773235
- Title: Online Resource Allocation with an Endogenous Markov State: Fewer LP Solves Earn More
- Title（参考訳）: 内因性マルコフ状態をもつオンライン資源配分:LPSの出現は少なかった
- Abstract要約: 有限水平オンラインリソースアロケーションをi.d.リクエストと内在的マルコフ状態を用いて検討する。
頻度の低いスキームは、既知と推定の両方で支配的のままである。
- 参考スコア（独自算出の注目度）: 1.9338739291800893
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study finite-horizon online resource allocation with i.i.d. requests and an endogenous Markov state on a finite state space: each action affects the transition of the state that governs future rewards and resource consumption. In this problem, a transient fluid LP benchmark upper bounds the expected reward of every nonanticipating policy, while a stationary LP supplies randomized state-dependent controls. We assume that the stationary LP has a unique optimum and identify primal nondegeneracy and irreducibility of the optimal induced kernel as important regularity conditions in this framework. With a known request prior, we show that, under nondegeneracy and irreducibility, both frequent and infrequent re-solving attain $O(1)$ regret. However, under a degenerate optimum, irreducibility yields the sharp worst-case $Θ(\sqrt{T})$ rate for infrequent re-solving, while frequent re-solving can incur $Ω(T)$ regret. Thus, more frequent optimization can perform asymptotically worse. With an unknown request prior, we develop a three-phase U-shaped infrequent re-solving policy that coordinates learning and inventory correction with $O(\log\log T)$ LP solves. When the optimal induced kernel is irreducible and the algorithm is given the optimal target state class and a constant-cost entrance policy, it attains $O(1)$ regret under nondegeneracy and $O(\sqrt{T})$ regret under degeneracy. Without the target-class information, linear minimax regret is unavoidable. Numerical experiments further illustrate the instability of round-by-round re-solving relative to epoch-wise infrequent re-solving, show that thresholding greatly mitigates its loss, and find that infrequent schemes remain dominant under both known and estimated priors.
- Abstract（参考訳）: 有限次元要求と内在的マルコフ状態を用いた有限水平オンライン資源割り当てを有限状態空間上で研究し、各行動は将来の報酬と資源消費を管理する状態の遷移に影響を与える。
この問題において、過渡流体LPベンチマークは、予測しないすべてのポリシーの期待される報酬を上限とし、定常LPはランダム化された状態依存制御を提供する。
定常LPは、一意の最適性を持ち、最適誘導核の原始的非退化性と既約性を、この枠組みの重要な正則性条件として同定する。
既知の要求により、非退化性と既約性の下では、頻繁かつ頻繁な再解決の両方で、O(1)$後悔を達成できることが示される。
しかし、退化した最適条件の下では、非可約性は、頻繁な再解法において急激な最悪の場合の$(\sqrt{T})$レートを生じる一方、頻繁な再解法は$Ω(T)$後悔を引き起こす。
したがって、より頻繁な最適化は漸近的に悪化する可能性がある。
未知の要求を前にして,学習と在庫補正を$O(\log\log T)$ LP解決と協調する3相U字の頻繁な再解法を開発した。
最適誘導されたカーネルが既約であり、アルゴリズムが最適目標状態クラスと一定のコストの入り口ポリシーを与えられると、非退化条件下では$O(1)$後悔、退化条件下では$O(\sqrt{T})$後悔となる。
ターゲットクラス情報がなければ、リニアミニマックス後悔は避けられない。
数値実験により, 急激な非定常再溶解に対する円周再溶解の不安定性がさらに説明され, しきい値の低下が著しく軽減され, 未知のスキームが既知と推定の両方で支配的であることが確認された。
関連論文リスト
- Learning Infinite-Horizon Average-Reward CMDPs via State Augmentation [0.8984888893275712]
本稿では, 無限水平平均逆制約マルコフ決定過程(CMDP)について, 弱い通信仮定の下で検討する。
計算効率のよい最初のアルゴリズムを提案し、高い確率で$widetildemathcalO(sqrtT)$ regretと累積制約違反を実現する。
論文 参考訳（メタデータ） (2026-09-30T06:31:55Z) - Constrained Online Learning with Noisy Constraint Values [55.29259818039367]
一般的な実現可能性の下では、我々のLEDGERアルゴリズムは、期待される損失$O(sqrt T)と期待される予算違反$O(sqrtTlog(eT))を達成します。
スレーター条件、フィードバックチャネル間の独立性、絶対的制約値境界は不要である。
論文 参考訳（メタデータ） (2026-09-07T01:38:41Z) - Near-Constant Strong Violation and Last-Iterate Convergence for Online CMDPs via Decaying Safety Margins [31.581870065866568]
制約付きマルコフ決定過程(CMDP)における安全なオンライン強化学習を,強い後悔と違反の指標の下で研究する。
サブリニアの強い報酬を後悔させる既存の原始二重法は、強い制約違反の増大を招いたり、あるいは固有振動による平均点収束に制限されたりしている。
本稿では,マルチ正規化探索(FlexDOME)アルゴリズムによるフレキシブルセーフティドメイン最適化を提案する。
論文 参考訳（メタデータ） (2026-02-11T14:54:26Z) - Online Markov Decision Processes with Terminal Law Constraints [10.878763806286157]
周期的フレームワークと呼ばれるリセットフリーのフレームワークを導入する。
目標は、累積損失を最小限に抑え、一定回数のステップ後にエージェントを初期状態分布に戻す周期的なポリシーを見つけることである。
2つのマルチエージェント設定で周期ポリシーを計算するための最初のアルゴリズムを示し、オーダー$tilde O(T3/4)$のサブ線形周期的後悔を実現する。
これは、M$均質なエージェントを$M > 1$と設定して、リセットなし学習に対する最初の漸近的でない保証を提供する。
論文 参考訳（メタデータ） (2026-01-12T12:46:12Z) - Decision from Suboptimal Classifiers: Excess Risk Pre- and Post-Calibration [52.70324949884702]
バッチ二分決定における近似的後続確率を用いた余剰リスクの定量化を行う。
我々は、再校正のみが後悔のほとんどに対処する体制と、後悔が集団的損失に支配される体制を識別する。
NLP実験では、これらの量によって、より高度なポストトレーニングの期待値が運用コストに値するかどうかが分かる。
論文 参考訳（メタデータ） (2025-03-23T10:52:36Z) - Non-stationary Delayed Online Convex Optimization: From Full-information to Bandit Setting [71.82716109461967]
遅延勾配が利用できる全情報ケースに対して Mild-OGD というアルゴリズムを提案する。
ミルド-OGDのダイナミックな後悔は、順番の仮定の下で$O(sqrtbardT(P_T+1))$で自動的に束縛されることを示す。
Mild-OGDのバンディット版も開発し,損失値の遅れのみを考慮に入れた,より困難なケースについて検討した。
論文 参考訳（メタデータ） (2023-05-20T07:54:07Z) - Best of Both Worlds Policy Optimization [33.13041034490332]
本稿では,正則化器,探索ボーナス,学習率を適切に設計することにより,損失が相反する場合には,より好意的なポリログ$(T)=後悔が得られることを示す。
政策最適化のために、ギャップ依存のポリログ$(T)$後悔境界が示されるのはこれが初めてである。
論文 参考訳（メタデータ） (2023-02-18T19:46:11Z) - Contextual Decision-Making with Knapsacks Beyond the Worst Case [5.65888994172721]
資源制約を伴う動的意思決定シナリオの枠組みについて検討する。
このフレームワークでは、エージェントがランダムな要求を観察すると、各ラウンドでアクションを選択する。
我々のアルゴリズムは最悪の場合であっても、ほぼ最適の$widetildeO(sqrtT)$ regretを維持していることを証明している。
論文 参考訳（メタデータ） (2022-11-25T08:21:50Z) - Benign Underfitting of Stochastic Gradient Descent [72.38051710389732]
本研究では,適切な学習データを得ることで,一般化性能を実現する「従来型」学習ルールとして,勾配降下度(SGD)がどの程度理解されるかを検討する。
類似現象が起こらない近縁な交換SGDを解析し、その集団リスクが実際に最適な速度で収束することを証明する。
論文 参考訳（メタデータ） (2022-02-27T13:25:01Z) - ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。
我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。
有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
論文 参考訳（メタデータ） (2020-08-28T14:46:56Z) - Dynamic Regret of Convex and Smooth Functions [93.71361250701075]
非定常環境におけるオンライン凸最適化について検討する。
パフォーマンス指標として動的後悔を選択します。
本研究では, 滑らかさを活かして, 動的後悔をさらに高めることが可能であることを示す。
論文 参考訳（メタデータ） (2020-07-07T14:10:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。