論文の概要: Wait-Less Offline Tuning and Re-solving for Online Decision Making
- arxiv url: http://arxiv.org/abs/2412.09594v2
- Date: Fri, 10 Jan 2025 09:40:04 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-01-13 15:25:14.367991
- Title: Wait-Less Offline Tuning and Re-solving for Online Decision Making
- Title（参考訳）: オンライン意思決定のためのオフラインチューニングと再解決
- Authors: Jingruo Sun, Wenzhi Gao, Ellen Vitercik, Yinyu Ye,
- Abstract要約: LP法と1次LP法の長所を組み合わせた新しいアルゴリズムを提案する。
我々のアルゴリズムは、$mathscrO(log (T/f) + sqrtf)$ regretを達成し、「待機なし」オンライン意思決定プロセスを提供する。
- 参考スコア（独自算出の注目度）: 10.984414655748095
- License:
- Abstract: Online linear programming (OLP) has found broad applications in revenue management and resource allocation. State-of-the-art OLP algorithms achieve low regret by repeatedly solving linear programming (LP) subproblems that incorporate updated resource information. However, LP-based methods are computationally expensive and often inefficient for large-scale applications. In contrast, recent first-order OLP algorithms are more computationally efficient but typically suffer from worse regret guarantees. To address these shortcomings, we propose a new algorithm that combines the strengths of LP-based and first-order OLP methods. The algorithm re-solves the LP subproblems periodically at a predefined frequency $f$ and uses the latest dual prices to guide online decision-making. In addition, a first-order method runs in parallel during each interval between LP re-solves, smoothing resource consumption. Our algorithm achieves $\mathscr{O}(\log (T/f) + \sqrt{f})$ regret, delivering a "wait-less" online decision-making process that balances the computational efficiency of first-order methods and the superior regret guarantee of LP-based methods.
- Abstract（参考訳）: オンライン線形プログラミング(OLP)は、収益管理と資源配分に幅広い応用を見出している。
最新のALPアルゴリズムは、更新されたリソース情報を組み込んだリニアプログラミング(LP)サブプロブレムを何度も解くことで、低遅延を実現する。
しかし、LPベースの手法は計算コストが高く、大規模アプリケーションでは非効率であることが多い。
対照的に、最近の一階OLPアルゴリズムはより計算効率が良いが、典型的には残念な保証に悩まされる。
これらの欠点に対処するために,LP法と1次LP法の長所を組み合わせた新しいアルゴリズムを提案する。
このアルゴリズムは、LPサブプロブレムを予め定義された周波数$f$で周期的に解決し、最新の2値を使ってオンライン意思決定をガイドする。
さらに,LP再溶出間隔毎に1次法が並列に実行され,資源消費の円滑化が図られる。
我々のアルゴリズムは、一階法の計算効率とLPベースの手法の優れた後悔保証とをバランスさせる「待機なし」オンライン意思決定プロセスを提供することで、後悔の意を表す$\mathscr{O}(\log (T/f) + \sqrt{f})を達成している。
関連論文リスト
- Infrequent Resolving Algorithm for Online Linear Programming [3.247415064064425]
既存のオンライン線形プログラミング(OLP)アルゴリズムは、LPベースアルゴリズムとLPフリーアルゴリズムの2つのカテゴリに分類される。
本稿では,LPを時間的水平線上でのO(loglog T)$倍だけ解きながら,常に後悔するアルゴリズムを提案する。
我々のアルゴリズムは、LPの$O(loglog T)$ timesと$Oleft(T(1/2+epsilon)Mright)$ regretを、LPの$M$ timesを解くことで、絶え間ない後悔を保証できる。
論文 参考訳（メタデータ） (2024-08-01T11:09:01Z) - Truly No-Regret Learning in Constrained MDPs [61.78619476991494]
未知のCMDPで学習するモデルベース原始双対アルゴリズムを提案する。
提案アルゴリズムは,誤差のキャンセルを伴わずにサブ線形後悔を実現する。
論文 参考訳（メタデータ） (2024-02-24T09:47:46Z) - Decoupling Learning and Decision-Making: Breaking the $\mathcal{O}(\sqrt{T})$ Barrier in Online Resource Allocation with First-Order Methods [7.518108920887426]
意思決定から学習を分離する新しいアルゴリズムフレームワークを導入する。
初めて、この新しいフレームワークで、一階述語メソッドが、$mathcalO(sqrtT)$を後悔できることを示す。
論文 参考訳（メタデータ） (2024-02-11T05:35:50Z) - Proximal Point Imitation Learning [48.50107891696562]
我々は、無限地平線模倣学習のための厳密な効率保証を備えた新しいアルゴリズムを開発した。
我々は、最適化、特に近点法(PPM)と双対平滑化から古典的ツールを活用する。
線形関数とニューラルネットワーク関数の近似の双方に対して、説得力のある経験的性能を実現する。
論文 参考訳（メタデータ） (2022-09-22T12:40:21Z) - Learning to Reformulate for Linear Programming [11.628932152805724]
本稿では,リニアプログラミング(LP)の強化学習に基づく再構成手法を提案する。
本研究では,2つの公共研究用LPデータセットと,実運用シナリオから収集した大規模LPデータセットに対して提案手法を実装した。
論文 参考訳（メタデータ） (2022-01-17T04:58:46Z) - Nearly Optimal Linear Convergence of Stochastic Primal-Dual Methods for
Linear Programming [5.126924253766052]
提案手法は,高い確率で鋭いインスタンスを解くための線形収束率を示す。
また、制約のない双線型問題に対する効率的な座標ベースのオラクルを提案する。
論文 参考訳（メタデータ） (2021-11-10T04:56:38Z) - Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic Algorithm for Constrained Markov Decision Processes [13.908826484332282]
そこで我々は,コストの抑えられたマルコフ決定プロセス問題を解決するために,オンライン・プリマル・デュアル・アクター・クリティカル法について検討した。
本稿では,CMDP問題の解法として,オンライン・プリマル・デュアル・アクター・クリティカル法の有限時間複雑性を初めて検討した。
論文 参考訳（メタデータ） (2021-10-21T18:05:40Z) - Fast and Complete: Enabling Complete Neural Network Verification with
Rapid and Massively Parallel Incomplete Verifiers [112.23981192818721]
BaB プロセス中に線形計画法 (LP) を置き換えるために, 逆モード線形緩和に基づく解析法 (LiRPA) を提案する。
LPとは異なり、LiRPAを適用すると、より弱い境界が得られ、分割時にサブドメインのコンフリクトをチェックすることもできない。
既存のLPベースのアプローチと比較して、桁違いのスピードアップを示す。
論文 参考訳（メタデータ） (2020-11-27T16:42:12Z) - Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。
この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。
古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
論文 参考訳（メタデータ） (2020-07-01T18:43:32Z) - Sparsified Linear Programming for Zero-Sum Equilibrium Finding [89.30539368124025]
我々は、この問題に対して全く異なるアプローチを示し、それは競争力があり、しばしば、以前の最先端技術よりも桁違いに優れている。
ポーカーエンドゲームの実験により、現代の線形プログラムソルバは、ゲーム固有のCFRの現代的な変種でさえも競合することを示した。
論文 参考訳（メタデータ） (2020-06-05T13:48:26Z) - Determinantal Point Processes in Randomized Numerical Linear Algebra [80.27102478796613]
数値線形代数(RandNLA)は、科学計算、データサイエンス、機械学習などで発生する行列問題に対する改良されたアルゴリズムを開発するためにランダム性を使用する。
最近の研究により、DPPとRandNLAの間の深い実りある関係が明らかになり、新たな保証とアルゴリズムの改善につながった。
論文 参考訳（メタデータ） (2020-05-07T00:39:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。