論文の概要: Optimally Pacing Budget Spending and Learning
- arxiv url: http://arxiv.org/abs/2610.11074v1
- Date: Thu, 08 Oct 2026 01:32:09 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-10 02:36:53.726971
- Title: Optimally Pacing Budget Spending and Learning
- Title（参考訳）: 予算の分散と学習を最適化する
- Abstract要約: 我々は、このスケジュールの累積支出が$D$の範囲内にあるすべての専門家に対して、後悔の$O(D sqrtlog F+ sqrtTlog F)$を得る完全情報アルゴリズムを提供する。
これは私たちが認識している最初のアルゴリズムで、そのようなタスクに対して$o(sqrtT)$保証を達成できます。
- 参考スコア（独自算出の注目度）: 19.32621537108768
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We establish near-optimal regret bounds for budget-constrained online learning against arbitrary classes of budget-pacing experts in the adversarial setting. In particular, given any class of $F$ experts and a candidate budget pacing schedule, we provide a full-information algorithm which obtains regret $O(D \sqrt{\log F}+ \sqrt{T\log F})$ against all experts whose cumulative spending stays within distance $D$ of this schedule, matching lower bounds established by Braverman et al. (2025). We additionally show that our technique extends to various problems in online resource allocation, where the learner gets to see the rewards and costs of the current options available to them, and establish $O(D\sqrt{\log F})$ regret bounds when fractional allocation is allowed. This is the first algorithm we are aware of which can achieve $o(\sqrt{T})$ guarantees for such tasks.
- Abstract（参考訳）: 我々は、予算制約のあるオンライン学習において、敵対的な状況下での予算削減の専門家の任意のクラスに対して、ほぼ最適に後悔する境界を定めている。
特に、あらゆる種類の$F$の専門家と候補予算のスケジュールが与えられた場合、Braverman et al (2025)によって確立された下限と一致する、累積的な支出がこのスケジュールの範囲内にあるすべての専門家に対して、後悔する$O(D \sqrt{\log F}+ \sqrt{T\log F})$を得る完全な情報アルゴリズムを提供する。
また,本手法はオンラインリソース割り当てにおいて,学習者が現在利用可能な選択肢の報酬やコストを把握し,分数割当が許された場合の後悔条件として$O(D\sqrt{\log F})$$O(D\sqrt{\log F})を設定できるような様々な問題にも適用可能であることを示す。
これは私たちが認識している最初のアルゴリズムであり、そのようなタスクに対する$o(\sqrt{T})$保証を達成することができる。
関連論文リスト
- Finite and Corruption-Robust Regret Bounds in Online Inverse Linear Optimization under M-Convex Action Sets [27.973926244529267]
本研究では,コンテキストレコメンデーションとして知られる逆逆線形最適化について検討する。
学習者は、M-集合上の最適解のキャラクタリゼーションとボリューム引数を組み合わせることで、これを後悔する。
論文 参考訳（メタデータ） (2026-02-02T05:48:54Z) - UCB-type Algorithm for Budget-Constrained Expert Learning [71.67657715154034]
algnameM-LCBはUCBスタイルのメタアルゴリズムであり、幻想的後悔の保証を提供する
我々は、AlgnameM-LCBが、限られたリソースの下で、ステートフルで自己学習の専門家をコーディネートする、より現実的なシナリオまで、古典的な帯域幅パラダイムをどのように拡張しているかを示す。
論文 参考訳（メタデータ） (2025-10-26T12:36:17Z) - Online Learning for Approximately-Convex Functions with Long-term Adversarial Constraints [8.314956969778692]
本研究では, 長期的予算制約を伴うオンライン学習問題を, 対戦環境において検討する。
この問題では、各ラウンド$t$で、学習者は凸集合からアクションを選択し、その後、相手がコスト関数を明らかにする。
提案手法は, 保証を改善した$textttAdversas$問題に対して, 効率的なソリューションを提供する。
論文 参考訳（メタデータ） (2025-08-23T11:21:24Z) - No-Regret Learning Under Adversarial Resource Constraints: A Spending Plan Is All You Need! [56.80767500991973]
アクション選択の前に報酬とコストが観測される$(i)$オンラインリソース割当と、アクション選択後、完全なフィードバックや盗賊フィードバックの下で、リソース制限付きオンライン学習である$(ii)$オンラインリソース割当に焦点を当てた。
報酬とコスト分布が時間とともに任意に変化する場合、これらの設定でサブ線形後悔を達成することは不可能であることが知られている。
我々は、支出計画に従う基準線に対する半線形後悔を実現する一般的な(基本的)二重的手法を設計し、また、支出計画が予算のバランスの取れた配分を保証すると、アルゴリズムの性能が向上する。
論文 参考訳（メタデータ） (2025-06-16T08:42:31Z) - Learning to Cover: Online Learning and Optimization with Irreversible Decisions [50.5775508521174]
我々は,個別かつ不可逆な意思決定を対象とするオンライン学習と最適化の問題を定義した。
各期間において、意思決定者は、オープンする施設を選択し、それぞれの成功に関する情報を受け取り、将来の決定を導くために分類モデルを更新する。
目的は,多数の施設を対象とする地平線を特徴とし,カバー対象を反映するチャンス制約の下で施設開口を最小化することである。
論文 参考訳（メタデータ） (2024-06-20T23:00:25Z) - Online Apprenticeship Learning [58.45089581278177]
見習い学習(AL)では、コスト関数にアクセスせずにマルコフ決定プロセス(MDP)が与えられます。
目標は、事前に定義されたコスト関数のセットで専門家のパフォーマンスに一致するポリシーを見つけることです。
ミラー下降型ノンレグレットアルゴリズムを2つ組み合わせることで,OAL問題を効果的に解くことができることを示す。
論文 参考訳（メタデータ） (2021-02-13T12:57:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。