論文の概要: No-Regret Learning Under Adversarial Resource Constraints: A Spending Plan Is All You Need!

• arxiv url: http://arxiv.org/abs/2506.13244v3
• Date: Wed, 18 Jun 2025 14:04:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-19 13:10:45.366126
• Title: No-Regret Learning Under Adversarial Resource Constraints: A Spending Plan Is All You Need!
• Title（参考訳）: 敵対的資源制約下での非回帰学習 - 提案計画がすべて必要である!
• Authors: Francesco Emanuele Stradi, Matteo Castiglioni, Alberto Marchesi, Nicola Gatti, Christian Kroer,
• Abstract要約: アクション選択の前に報酬とコストが観測される$(i)$オンラインリソース割当と、アクション選択後、完全なフィードバックや盗賊フィードバックの下で、リソース制限付きオンライン学習である$(ii)$オンラインリソース割当に焦点を当てた。 報酬とコスト分布が時間とともに任意に変化する場合、これらの設定でサブ線形後悔を達成することは不可能であることが知られている。 我々は、支出計画に従う基準線に対する半線形後悔を実現する一般的な(基本的)二重的手法を設計し、また、支出計画が予算のバランスの取れた配分を保証すると、アルゴリズムの性能が向上する。
• 参考スコア（独自算出の注目度）: 56.80767500991973
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study online decision making problems under resource constraints, where both reward and cost functions are drawn from distributions that may change adversarially over time. We focus on two canonical settings: $(i)$ online resource allocation where rewards and costs are observed before action selection, and $(ii)$ online learning with resource constraints where they are observed after action selection, under full feedback or bandit feedback. It is well known that achieving sublinear regret in these settings is impossible when reward and cost distributions may change arbitrarily over time. To address this challenge, we analyze a framework in which the learner is guided by a spending plan--a sequence prescribing expected resource usage across rounds. We design general (primal-)dual methods that achieve sublinear regret with respect to baselines that follow the spending plan. Crucially, the performance of our algorithms improves when the spending plan ensures a well-balanced distribution of the budget across rounds. We additionally provide a robust variant of our methods to handle worst-case scenarios where the spending plan is highly imbalanced. To conclude, we study the regret of our algorithms when competing against benchmarks that deviate from the prescribed spending plan.
• Abstract（参考訳）: 資源制約下でのオンライン意思決定問題について検討し、報酬関数とコスト関数は、時間とともに逆転する可能性のある分布から引き出される。 私たちは2つの標準設定に焦点を当てています。 (i)アクション選択の前に報酬とコストが観察されるオンラインリソース割当及び$ (ii) 行動選択後, 完全なフィードバック, 包括的フィードバック下において, リソース制約によるオンライン学習を行う。 報酬とコスト分布が時間とともに任意に変化する場合、これらの設定でサブ線形後悔を達成することは不可能であることが知られている。 この課題に対処するために、学習者が支出計画によってガイドされるフレームワーク、つまり、ラウンド全体で期待されるリソース使用量を規定するシーケンスを分析します。 我々は、支出計画に従う基準線に関して、サブリニアな後悔を実現する一般的な(最優先の)二重手法を設計する。 重要なことに、我々のアルゴリズムの性能は、支出計画がラウンドごとの予算のバランスの取れた分布を確実にするときに向上する。 さらに、支出計画が極めて不均衡な最悪のシナリオを扱うために、我々の方法の堅牢なバリエーションも提供します。 結論として、所定の支出計画から逸脱したベンチマークと競合する際のアルゴリズムの後悔について検討する。

関連論文リスト

• Learning to Price with Resource Constraints: From Full Information to Machine-Learned Prices [13.68761797358598]
  我々はknapsackによる動的価格問題について検討し、資源制約下での探索と利用のバランスをとることの課題に対処する。 本稿では, 事前情報を持たないシナリオを対象としたオンライン学習アルゴリズムと, 予測誤りを既知の上限付きマシン学習情報量を利用した推定-then-select re-solveアルゴリズムの3つのアルゴリズムを紹介する。
  論文  参考訳（メタデータ） (2025-01-24T00:46:52Z)
• Learning to Cover: Online Learning and Optimization with Irreversible Decisions [50.5775508521174]
  我々は,個別かつ不可逆な意思決定を対象とするオンライン学習と最適化の問題を定義した。 各期間において、意思決定者は、オープンする施設を選択し、それぞれの成功に関する情報を受け取り、将来の決定を導くために分類モデルを更新する。 目的は,多数の施設を対象とする地平線を特徴とし,カバー対象を反映するチャンス制約の下で施設開口を最小化することである。
  論文  参考訳（メタデータ） (2024-06-20T23:00:25Z)
• Online Learning with Costly Features in Non-stationary Environments [6.009759445555003]
  シーケンシャルな意思決定の問題では、長期的な報酬を最大化することが第一の目標である。 現実世界の問題では、有益な情報を集めるのにしばしばコストがかかる。 時間内にサブ線形後悔を保証するアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2023-07-18T16:13:35Z)
• A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
  我々は,意思決定者が長期的制約の対象となる一連の意思決定をしなければならないオンライン学習問題について検討する。 目標は、全報酬を最大化し、同時に、$T$ラウンド全体で小さな累積違反を達成することである。 本稿では,この一般クラス問題に対して,未知のモデルに基づいて報酬と制約が選択された場合と,各ラウンドで敵が選択した場合の双方において,最良世界型アルゴリズムを提示する。
  論文  参考訳（メタデータ） (2022-09-15T16:59:19Z)
• Online Learning with Knapsacks: the Best of Both Worlds [54.28273783164608]
  オンライン学習の課題として,意思決定者が,リソース制約の有限セットに違反することなく,期待する報酬を最大化したい,という課題を提起する。 当社のフレームワークは,意思決定者がそのエビデンスを柔軟かつコスト論的に扱えるようにします。
  論文  参考訳（メタデータ） (2022-02-28T12:10:48Z)
• Dynamic Planning and Learning under Recovering Rewards [18.829837839926956]
  我々は「純粋周期ポリシー」のクラスの性能保証を提案し、構築し、証明する。 私たちのフレームワークとポリシー設計は、他のオフライン計画およびオンライン学習アプリケーションに適応する可能性がある。
  論文  参考訳（メタデータ） (2021-06-28T15:40:07Z)
• Confidence-Budget Matching for Sequential Budgeted Learning [69.77435313099366]
  問合せ予算で意思決定問題を定式化する。 我々は,多腕バンディット,線形バンディット,強化学習問題を考察する。 我々は,CBMに基づくアルゴリズムが逆性の存在下で良好に動作することを示す。
  論文  参考訳（メタデータ） (2021-02-05T19:56:31Z)
• Online Stochastic Optimization with Wasserstein Based Non-stationarity [12.91020811577007]
  有限期間の地平線上の複数の予算制約を持つ一般的なオンライン最適化問題を検討する。 意思決定者の目標は、予算制約の対象となる累積報酬を最大化することである。 この定式化は、オンラインリニアプログラミングやネットワーク収益管理を含む幅広いアプリケーションを取り込む。
  論文  参考訳（メタデータ） (2020-12-13T04:47:37Z)
• Hierarchical Adaptive Contextual Bandits for Resource Constraint based Recommendation [49.69139684065241]
  コンテキスト多重武装バンディット(MAB)は、様々な問題において最先端のパフォーマンスを達成する。 本稿では,階層型適応型文脈帯域幅法(HATCH)を提案する。
  論文  参考訳（メタデータ） (2020-04-02T17:04:52Z)

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

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