論文の概要: A New Benchmark for Online Learning with Budget-Balancing Constraints

• arxiv url: http://arxiv.org/abs/2503.14796v1
• Date: Wed, 19 Mar 2025 00:14:20 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-20 15:22:00.210022
• Title: A New Benchmark for Online Learning with Budget-Balancing Constraints
• Title（参考訳）: 予算分散制約を考慮したオンライン学習のための新しいベンチマーク
• Authors: Mark Braverman, Jingyi Liu, Jieming Mao, Jon Schneider, Eric Xue,
• Abstract要約: 本稿では,オートバイディングなどの実世界の応用と,その基礎となる数学的構造を比較対象とする新しいベンチマークを提案する。 サブリニアな消費パターンが$o(T2)$以内である戦略に対して,サブリニアな後悔は達成可能であることを示す。
• 参考スコア（独自算出の注目度）: 14.818946657685267
• License:
• Abstract: The adversarial Bandit with Knapsack problem is a multi-armed bandits problem with budget constraints and adversarial rewards and costs. In each round, a learner selects an action to take and observes the reward and cost of the selected action. The goal is to maximize the sum of rewards while satisfying the budget constraint. The classical benchmark to compare against is the best fixed distribution over actions that satisfies the budget constraint in expectation. Unlike its stochastic counterpart, where rewards and costs are drawn from some fixed distribution (Badanidiyuru et al., 2018), the adversarial BwK problem does not admit a no-regret algorithm for every problem instance due to the "spend-or-save" dilemma (Immorlica et al., 2022). A key problem left open by existing works is whether there exists a weaker but still meaningful benchmark to compare against such that no-regret learning is still possible. In this work, we present a new benchmark to compare against, motivated both by real-world applications such as autobidding and by its underlying mathematical structure. The benchmark is based on the Earth Mover's Distance (EMD), and we show that sublinear regret is attainable against any strategy whose spending pattern is within EMD $o(T^2)$ of any sub-pacing spending pattern. As a special case, we obtain results against the "pacing over windows" benchmark, where we partition time into disjoint windows of size $w$ and allow the benchmark strategies to choose a different distribution over actions for each window while satisfying a pacing budget constraint. Against this benchmark, our algorithm obtains a regret bound of $\tilde{O}(T/\sqrt{w}+\sqrt{wT})$. We also show a matching lower bound, proving the optimality of our algorithm in this important special case. In addition, we provide further evidence of the necessity of the EMD condition for obtaining a sublinear regret.
• Abstract（参考訳）: クナプサック問題(Knapsack problem)は、予算の制約と敵の報酬とコストを伴う多武装のバンディット問題である。 各ラウンドで、学習者は、選択したアクションの報酬とコストを取り込み、観察するアクションを選択する。 目標は、予算の制約を満たしながら報酬の合計を最大化することです。 比較すべき古典的ベンチマークは、期待する予算制約を満たすアクションよりも最良の固定分布である。 いくつかの固定分布(Badanidiyuru et al , 2018)から報酬とコストが引き出される確率的問題とは異なり、逆BwK問題では、"spend-or-save"ジレンマ(Immorlica et al , 2022)により、全ての問題に対して非回帰アルゴリズムが認められない。 既存の研究で残された重要な問題は、未学習の学習がまだ可能であることを比較するために、より弱いがまだ意味のあるベンチマークが存在するかどうかである。 本研究では,オートバイディングなどの実世界の応用と,その基礎となる数学的構造を比較対象とする新しいベンチマークを提案する。 このベンチマークは、Earth Mover's Distance (EMD)に基づいており、サブライン的後悔は、EMD $o(T^2)$以下の支出パターンを持つ戦略に対して達成可能であることを示す。 特別な場合として、我々は "pacing over windows" ベンチマークに対して、時間を$w$の非結合ウィンドウに分割し、ベンチマーク戦略が予算制約を満たすことなく、各ウィンドウに対するアクション上の異なる分布を選択できるようにする。 このベンチマークに対して、我々のアルゴリズムは、$\tilde{O}(T/\sqrt{w}+\sqrt{wT})$の後悔境界を得る。 また、この重要な特別な場合において、アルゴリズムの最適性を証明し、一致した下界を示す。 さらに, サブリニアな後悔を得るためには, EMD 条件が必要であるという証拠も提示する。

関連論文リスト

• Rising Rested Bandits: Lower Bounds and Efficient Algorithms [15.390680055166769]
  本論文は、連続マルチアーマッドバンド(MAB)の分野である。 我々は,腕の期待される報酬が単調に非減少性であり,結束する残留包帯の特定の症例について検討した。 我々は,本アルゴリズムを実世界のデータセットに対するオンラインモデル選択問題や,複数の合成されたタスクに対する非定常MABの最先端手法と経験的に比較した。
  論文  参考訳（メタデータ） (2024-11-06T22:00:46Z)
• Variance-Dependent Regret Bounds for Non-stationary Linear Bandits [52.872628573907434]
  報酬分布の分散と$B_K$の分散を利用するアルゴリズムを提案する。 Restarted Weighted$textOFUL+$とRestarted$textSAVE+$の2つの新しいアルゴリズムを紹介します。 特に、V_K$が$K$よりはるかに小さい場合、我々のアルゴリズムは、異なる設定下での非定常線形バンドレットの最先端結果よりも優れている。
  論文  参考訳（メタデータ） (2024-03-15T23:36:55Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
  本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。 本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。 我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
  論文  参考訳（メタデータ） (2023-10-02T08:15:52Z)
• Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency [90.40062452292091]
  本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。 我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。 また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-21T00:17:24Z)
• Adversarially Robust Multi-Armed Bandit Algorithm with Variance-Dependent Regret Bounds [34.37963000493442]
  本稿では,マルチアーム・バンディット(MAB)問題について考察し,両対向的条件下でほぼ最適に機能する,新たなベスト・オブ・ボス・ワールド(BOBW)アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-06-14T12:58:46Z)
• Stochastic Linear Bandits Robust to Adversarial Attacks [117.665995707568]
  我々はロバスト位相除去アルゴリズムの2つの変種を提供し、その1つは$C$を知っており、もう1つはそうでない。 いずれの変種も、倒壊しない場合には、それぞれ$C = 0$ となり、それぞれ追加の加法項が生じる。 文脈的設定では、単純な欲求的アルゴリズムは、明示的な探索を行わず、C$を知らないにもかかわらず、ほぼ最適加法的後悔項で証明可能な堅牢性を示す。
  論文  参考訳（メタデータ） (2020-07-07T09:00:57Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)
• Budget-Constrained Bandits over General Cost and Reward Distributions [32.63624728528415]
  我々は,各アームがランダムなコストを発生させ,その見返りにランダムな報酬を与える,予算制約付きバンディット問題を考える。 ある$gamma > 0$ に対して位数 $(2+gamma)$ のモーメントが存在するならば、$O(log B)$ regret は予算 $B>0$ に対して達成可能である。
  論文  参考訳（メタデータ） (2020-02-29T23:50:08Z)

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

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