論文の概要: Beyond $\mathcal{O}(\sqrt{T})$ Regret: Decoupling Learning and Decision-making in Online Linear Programming

• arxiv url: http://arxiv.org/abs/2501.02761v1
• Date: Mon, 06 Jan 2025 04:57:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-07 17:08:20.117284
• Title: Beyond $\mathcal{O}(\sqrt{T})$ Regret: Decoupling Learning and Decision-making in Online Linear Programming
• Title（参考訳）: $\mathcal{O}(\sqrt{T})$ Regret: オンライン線形プログラミングにおける学習と意思決定の分離
• Authors: Wenzhi Gao, Dongdong Ge, Chenyu Xue, Chunlin Sun, Yinyu Ye,
• Abstract要約: 本稿では,LP双対問題が一定の誤差境界条件を示す場合に,$mathcalO ( sqrtT )$の結果を改善するための一般的な枠組みを確立する。 連続的なサポート設定において,1次学習アルゴリズムが$o(sqrtT )$後悔し,非退化仮定以外の有限サポート設定において$mathcalO (log T)$後悔することを示す。
• 参考スコア（独自算出の注目度）: 7.518108920887426
• License:
• Abstract: Online linear programming plays an important role in both revenue management and resource allocation, and recent research has focused on developing efficient first-order online learning algorithms. Despite the empirical success of first-order methods, they typically achieve a regret no better than $\mathcal{O} ( \sqrt{T} )$, which is suboptimal compared to the $\mathcal{O} (\log T)$ bound guaranteed by the state-of-the-art linear programming (LP)-based online algorithms. This paper establishes a general framework that improves upon the $\mathcal{O} ( \sqrt{T} )$ result when the LP dual problem exhibits certain error bound conditions. For the first time, we show that first-order learning algorithms achieve $o( \sqrt{T} )$ regret in the continuous support setting and $\mathcal{O} (\log T)$ regret in the finite support setting beyond the non-degeneracy assumption. Our results significantly improve the state-of-the-art regret results and provide new insights for sequential decision-making.
• Abstract（参考訳）: オンライン線形プログラミングは、収益管理と資源配分の両方において重要な役割を担い、近年では効率的な一階オンライン学習アルゴリズムの開発に重点を置いている。 一階法の実証的な成功にもかかわらず、それらは通常$\mathcal{O} ( \sqrt{T} )$よりも良い後悔を達成し、これは、最先端の線形プログラミング(LP)ベースのオンラインアルゴリズムによって保証される$\mathcal{O} (\log T)$よりも最適である。 本稿では、LP双対問題のある誤差境界条件を示す場合、$\mathcal{O} ( \sqrt{T} )$の結果を改善するための一般的な枠組みを確立する。 第一次学習アルゴリズムが連続的なサポート設定において$o( \sqrt{T} )$後悔し、非退化仮定以外の有限サポート設定において$\mathcal{O} (\log T)$後悔することを示す。 以上の結果から, 現状の後悔の結果を大幅に改善し, シーケンシャルな意思決定に新たな洞察を与えることができた。

関連論文リスト

• Infrequent Resolving Algorithm for Online Linear Programming [3.247415064064425]
  既存のオンライン線形プログラミング(OLP)アルゴリズムは、LPベースアルゴリズムとLPフリーアルゴリズムの2つのカテゴリに分類される。 本稿では,LPを数個の時間点で解き,他の時間点で1次計算を行うアルゴリズムを提案する。 本研究は,販売地平線の開始時と終了時の両方で解決する価値を強調し,提案方針の性能保証を証明するための新しい枠組みを提供する。
  論文  参考訳（メタデータ） (2024-08-01T11:09:01Z)
• 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)
• Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
  一般化線形モデル (GLM) フレームワークを用いて, citelu2021low で提案した一般化低ランク行列帯域問題について検討する。 既存のアルゴリズムの計算不可能性と理論的制約を克服するため,まずG-ESTTフレームワークを提案する。 G-ESTT は $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret を達成でき、G-ESTS は $tildeO を達成できることを示す。
  論文  参考訳（メタデータ） (2024-01-14T14:14:19Z)
• Non-stationary Projection-free Online Learning with Dynamic and Adaptive Regret Guarantees [36.746745619968024]
  本研究では,非定常プロジェクションフリーオンライン学習について検討し,動的後悔と適応的後悔を選択して評価を行った。 我々の結果は、プロジェクションフリーオンライン学習における最初の一般的な動的後悔境界であり、既存の$mathcalO(T3/4)$static regretを復元することができる。 本稿では,$tildemathcalO(tau3/4)$ アダプティブリフレッシュバウンドを長さ$tauの任意の間隔で達成するためのプロジェクションフリーな手法を提案する。
  論文  参考訳（メタデータ） (2023-05-19T15:02:10Z)
• Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
  我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。 本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-30T14:37:21Z)
• The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret and Policy Switches [84.54669549718075]
  漸進的強化学習(RL)における後悔の最小化問題について検討する。 一般関数クラスと一般モデルクラスで学ぶことに集中する。 対数的後悔境界は$O(log T)$スイッチングコストのアルゴリズムによって実現可能であることを示す。
  論文  参考訳（メタデータ） (2022-03-03T02:55:55Z)
• PDE-Based Optimal Strategy for Unconstrained Online Learning [40.61498562988079]
  部分微分方程式(PDE)を解くことによって時間変化ポテンシャル関数を生成するフレームワークを提案する。 我々のフレームワークは、いくつかの古典的なポテンシャルを回復し、より重要なことは、新しいものを設計するための体系的なアプローチを提供する。 これは最適なリード定数を持つ最初のパラメータフリーアルゴリズムである。
  論文  参考訳（メタデータ） (2022-01-19T22:21:21Z)
• Logarithmic Regret from Sublinear Hints [76.87432703516942]
  自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。 また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
  論文  参考訳（メタデータ） (2021-11-09T16:50:18Z)
• Online Linear Optimization with Many Hints [72.4277628722419]
  本研究では,学習者が決定に先立って各ラウンドでK$"hint"ベクトルにアクセス可能なオンライン線形最適化(OLO)問題について検討する。 この設定では、コストベクトルと正の相関を持つ$K$ヒントの凸結合が存在する場合、対数後悔を求めるアルゴリズムを考案する。
  論文  参考訳（メタデータ） (2020-10-06T23:25:05Z)
• Online Learning with Imperfect Hints [72.4277628722419]
  オンライン学習において,不完全な方向ヒントを用いたアルゴリズムを開発し,ほぼ一致している。 我々のアルゴリズムはヒントの品質を損なうものであり、後悔の限界は常に相関するヒントの場合と隠れない場合とを補間する。
  論文  参考訳（メタデータ） (2020-02-11T23:06:09Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。