論文の概要: Beyond Non-Degeneracy: Revisiting Certainty Equivalent Heuristic for Online Linear Programming
- arxiv url: http://arxiv.org/abs/2501.01716v2
- Date: Thu, 13 Feb 2025 00:33:06 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-14 13:43:57.285440
- Title: Beyond Non-Degeneracy: Revisiting Certainty Equivalent Heuristic for Online Linear Programming
- Title（参考訳）: 非汎用性を超えて:オンライン線形プログラミングにおける確実な等価ヒューリスティックを再考する
- Authors: Yilun Chen, Wenjia Wang,
- Abstract要約: この結果から,不確実性等価性は分布の微妙な仮定の下で一様に近い最適後悔を達成できることが示唆された。
以上の結果から,CE は従来の信念とは対照的に,幅広い問題事例に対する退化の呪いを効果的に打ち負かしていると考えられる。
これらの手法は、より広範なオンライン意思決定コンテキストにおける潜在的な応用を見出すことができる。
- 参考スコア（独自算出の注目度）: 18.371947752008744
- License:
- Abstract: The Certainty Equivalent heuristic (CE) is a widely-used algorithm for various dynamic resource allocation problems in OR and OM. Despite its popularity, existing theoretical guarantees of CE are limited to settings satisfying restrictive fluid regularity conditions, particularly, the non-degeneracy conditions, under the widely held belief that the violation of such conditions leads to performance deterioration and necessitates algorithmic innovation beyond CE. In this work, we conduct a refined performance analysis of CE within the general framework of online linear programming. We show that CE achieves uniformly near-optimal regret (up to a polylogarithmic factor in $T$) under only mild assumptions on the underlying distribution, without relying on any fluid regularity conditions. Our result implies that, contrary to prior belief, CE effectively beats the curse of degeneracy for a wide range of problem instances with continuous conditional reward distributions, highlighting the distinction of the problem's structure between discrete and non-discrete settings. Our explicit regret bound interpolates between the mild $(\log T)^2$ regime and the worst-case $\sqrt{T}$ regime with a parameter $\beta$ quantifying the minimal rate of probability accumulation of the conditional reward distributions, generalizing prior findings in the multisecretary setting. To achieve these results, we develop novel algorithmic analytical techniques. Drawing tools from the empirical processes theory, we establish strong concentration analysis of the solutions to random linear programs, leading to improved regret analysis under significantly relaxed assumptions. These techniques may find potential applications in broader online decision-making contexts.
- Abstract（参考訳）: Certainty Equivalent Heuristic (CE) はORとOMの様々な動的リソース割り当て問題に対して広く使われているアルゴリズムである。
その人気にもかかわらず、CEの既存の理論的保証は制限された流体の規則性条件を満たす設定に限られており、特に非退化条件は、そのような条件の違反がパフォーマンスの悪化を招き、CE以外のアルゴリズムの革新を必要とすると広く信じられている。
本研究では,オンライン線形プログラミングの一般的な枠組みの中で,CEの洗練された性能解析を行う。
本研究は, 流動正則性条件に頼らずに, CEが一様に最適に近い後悔(T$のポリ対数係数まで)を達成することを示す。
以上の結果から,CE は従来の信念とは対照的に,連続的な条件付き報酬分布を持つ幅広い問題事例に対する縮退の呪いを効果的に打ち負かし,離散的および非離散的セッティング間の問題構造の違いを強調した。
我々の明示的な後悔は、控えめな$(\log T)^2$ regime と最悪の$\sqrt{T}$ regime の間の補間であり、パラメータ $\beta$ は条件付き報酬分布の確率蓄積の最小速度を定量化し、マルチシークレット設定における事前の発見を一般化する。
これらの結果を得るために,新しいアルゴリズム解析手法を開発した。
経験的プロセス理論からツールを描画し、ランダムな線形プログラムに対する解の強い濃度解析を確立し、非常に緩やかな仮定の下で後悔の分析を改善する。
これらの手法は、より広範なオンライン意思決定コンテキストにおける潜在的な応用を見出すことができる。
関連論文リスト
- Model-Based Epistemic Variance of Values for Risk-Aware Policy Optimization [59.758009422067]
モデルベース強化学習における累積報酬に対する不確実性を定量化する問題を考察する。
我々は、解が値の真後分散に収束する新しい不確実性ベルマン方程式(UBE)を提案する。
本稿では,リスク・サーキングとリスク・アバース・ポリシー最適化のいずれにも適用可能な汎用ポリシー最適化アルゴリズムQ-Uncertainty Soft Actor-Critic (QU-SAC)を導入する。
論文 参考訳（メタデータ） (2023-12-07T15:55:58Z) - f-FERM: A Scalable Framework for Robust Fair Empirical Risk Minimization [9.591164070876689]
本稿では、f-divergence measures(f-FERM)に基づく公正な経験的リスクに対する統一的な最適化フレームワークを提案する。
さらに,f-FERMによるほぼ全てのバッチサイズに対するフェアネス・精度トレードオフの優位性を実証した。
我々の拡張は、不確実集合として$L_p$ノルムの下で f-FERM の目的を分布的に頑健に最適化する手法に基づいている。
論文 参考訳（メタデータ） (2023-12-06T03:14:16Z) - Distributionally Robust Optimization with Bias and Variance Reduction [9.341215359733601]
勾配に基づくアルゴリズムであるProspectは、スムーズな正規化損失に対する線形収束を享受していることを示す。
また、勾配法のようなベースラインよりも2～3$times$早く収束できることも示している。
論文 参考訳（メタデータ） (2023-10-21T00:03:54Z) - A Robustness Analysis of Blind Source Separation [91.3755431537592]
ブラインドソース分離(BSS)は、変換$f$が可逆であるが未知であるという条件の下で、その混合である$X=f(S)$から観測されていない信号を復元することを目的としている。
このような違反を分析し、その影響を$X$から$S$のブラインドリカバリに与える影響を定量化するための一般的なフレームワークを提案する。
定義された構造的仮定からの偏差に対する一般的なBSS溶出は、明示的な連続性保証という形で、利益的に分析可能であることを示す。
論文 参考訳（メタデータ） (2023-03-17T16:30:51Z) - Learning to Optimize with Stochastic Dominance Constraints [103.26714928625582]
本稿では,不確実量を比較する問題に対して,単純かつ効率的なアプローチを開発する。
我々はラグランジアンの内部最適化をサロゲート近似の学習問題として再考した。
提案したライト-SDは、ファイナンスからサプライチェーン管理に至るまで、いくつかの代表的な問題において優れた性能を示す。
論文 参考訳（メタデータ） (2022-11-14T21:54:31Z) - Linear Stochastic Bandits over a Bit-Constrained Channel [37.01818450308119]
我々は,ビット制約チャネル上に線形バンドレットの新たな定式化を導入する。
サーバの目標は、未知のモデルパラメータの推定値に基づいてアクションを取ることで、累積的後悔を最小限に抑えることである。
未知のモデルが$d$-dimensionalである場合、チャネル容量は$O(d)$ bits suffices で順序最適後悔を実現する。
論文 参考訳（メタデータ） (2022-03-02T15:54:03Z) - Instance-Dependent Confidence and Early Stopping for Reinforcement
Learning [99.57168572237421]
強化学習(RL)のための様々なアルゴリズムは、その収束率の劇的な変動を問題構造の関数として示している。
この研究は、観察されたパフォーマンスの違いについて、textitexを説明する保証を提供する。
次の自然なステップは、これらの理論的保証を実際に有用なガイドラインに変換することです。
論文 参考訳（メタデータ） (2022-01-21T04:25:35Z) - Online Allocation with Two-sided Resource Constraints [44.5635910908944]
我々は,要求が順次到着する,リソース制約の低いオンラインアロケーション問題を考える。
提案手法では, リクエスト全体を知るオフライン問題に対して, 1-O (fracepsilonalpha-epsilon)$-competitive ratioを求めるアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-12-28T02:21:06Z) - A general sample complexity analysis of vanilla policy gradient [101.16957584135767]
政策勾配(PG)は、最も一般的な強化学習(RL)問題の1つである。
PG軌道の「バニラ」理論的理解は、RL問題を解く最も一般的な方法の1つである。
論文 参考訳（メタデータ） (2021-07-23T19:38:17Z) - Amortized Conditional Normalized Maximum Likelihood: Reliable Out of
Distribution Uncertainty Estimation [99.92568326314667]
本研究では,不確実性推定のための拡張性のある汎用的アプローチとして,償却条件正規化最大値(ACNML)法を提案する。
提案アルゴリズムは条件付き正規化最大度(CNML)符号化方式に基づいており、最小記述長の原理に従って最小値の最適特性を持つ。
我々は、ACNMLが、分布外入力のキャリブレーションの観点から、不確実性推定のための多くの手法と好意的に比較することを示した。
論文 参考訳（メタデータ） (2020-11-05T08:04:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。