論文の概要: Bandits with Replenishable Knapsacks: the Best of both Worlds

• arxiv url: http://arxiv.org/abs/2306.08470v1
• Date: Wed, 14 Jun 2023 12:34:00 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-16 19:09:43.497384
• Title: Bandits with Replenishable Knapsacks: the Best of both Worlds
• Title（参考訳）: 再現可能なナップサックのバンディット:両世界のベスト
• Authors: Martino Bernasconi, Matteo Castiglioni, Andrea Celli, Federico Fusco
• Abstract要約: 非単調な資源利用を可能にするBwKフレームワークの自然な一般化について検討する。 入力モデルの下で、我々のアルゴリズムはインスタンスに依存しない $tildeO(T1/2)$ regret bound を生成する。
• 参考スコア（独自算出の注目度）: 26.786438972889208
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The bandits with knapsack (BwK) framework models online decision-making problems in which an agent makes a sequence of decisions subject to resource consumption constraints. The traditional model assumes that each action consumes a non-negative amount of resources and the process ends when the initial budgets are fully depleted. We study a natural generalization of the BwK framework which allows non-monotonic resource utilization, i.e., resources can be replenished by a positive amount. We propose a best-of-both-worlds primal-dual template that can handle any online learning problem with replenishment for which a suitable primal regret minimizer exists. In particular, we provide the first positive results for the case of adversarial inputs by showing that our framework guarantees a constant competitive ratio $\alpha$ when $B=\Omega(T)$ or when the possible per-round replenishment is a positive constant. Moreover, under a stochastic input model, our algorithm yields an instance-independent $\tilde{O}(T^{1/2})$ regret bound which complements existing instance-dependent bounds for the same setting. Finally, we provide applications of our framework to some economic problems of practical relevance.
• Abstract（参考訳）: knapsack(bwk)フレームワークのバンディットは、エージェントがリソース消費の制約に従う一連の決定を下すオンライン意思決定問題をモデル化する。 従来のモデルでは、各アクションが非負のリソースを消費し、初期予算が完全に枯渇するとプロセスが終了する。 本研究では,非単調な資源利用を可能にするbwkフレームワークの自然一般化,すなわち資源を正の量で補充できる方法を検討する。 そこで本稿では,オンライン学習問題に対処できる最強のプリミティブ・デュアルテンプレートを提案する。 特に、我々のフレームワークは、$b=\omega(t)$ または可能な1ラウンドあたりの補充が正の定数である場合に、一定の競合比 $\alpha$ を保証していることを示すことによって、敵対的入力の場合の最初のポジティブな結果を提供する。 さらに,確率的入力モデルの下では,既存のインスタンス依存境界を補完するインスタンス独立$\tilde{O}(T^{1/2})$ regret boundが得られる。 最後に,我々の枠組みを実践的妥当性の経済的問題に適用する。

関連論文リスト

• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Online Learning under Budget and ROI Constraints via Weak Adaptivity [57.097119428915796]
  制約付きオンライン学習問題に対する既存の原始双対アルゴリズムは、2つの基本的な仮定に依存している。 このような仮定は、標準の原始双対テンプレートを弱適応的後悔最小化器で与えることによって、どのように回避できるのかを示す。 上記の2つの前提が満たされていない場合に保証される、世界の最高の保証を証明します。
  論文  参考訳（メタデータ） (2023-02-02T16:30:33Z)
• Stochastic Rising Bandits [40.32303434592863]
  本研究は、腕が単調に非減少している、安静時および安静時バンディットの特定の症例について検討する。 この特性により、ペイオフの規則性を利用して、厳密な後悔の限界を提供する、特別に構築されたアルゴリズムを設計することができる。 我々は,本アルゴリズムを実世界のデータセットに対するオンラインモデル選択問題や,複数の合成されたタスクに対する非定常MABの最先端手法と経験的に比較した。
  論文  参考訳（メタデータ） (2022-12-07T17:30:45Z)
• Constrained Pure Exploration Multi-Armed Bandits with a Fixed Budget [4.226118870861363]
  固定予算の下で、制約のある純粋な探索、多武装バンディットの定式化を検討する。 本稿では,Successive Rejects フレームワークに基づく textscConstrained-SR というアルゴリズムを提案する。 また, ある特別な場合において, 関連する崩壊速度は情報理論的下界に対してほぼ最適であることを示した。
  論文  参考訳（メタデータ） (2022-11-27T08:58:16Z)
• Non-monotonic Resource Utilization in the Bandits with Knapsacks Problem [6.227074051959886]
  knapsacks (BwK) を用いたバンドは、不確実性の下でのシーケンシャルな意思決定に影響を及ぼすモデルである。 非単調な資源利用を可能にするBwK問題の自然な一般化を導入する。
  論文  参考訳（メタデータ） (2022-09-24T14:02:05Z)
• A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
  我々は,意思決定者が長期的制約の対象となる一連の意思決定をしなければならないオンライン学習問題について検討する。 目標は、全報酬を最大化し、同時に、$T$ラウンド全体で小さな累積違反を達成することである。 本稿では,この一般クラス問題に対して,未知のモデルに基づいて報酬と制約が選択された場合と,各ラウンドで敵が選択した場合の双方において,最良世界型アルゴリズムを提示する。
  論文  参考訳（メタデータ） (2022-09-15T16:59:19Z)
• Non-stationary Bandits with Knapsacks [6.2006721306998065]
  非定常環境におけるクナプサック(BwK)による包帯問題について検討する。 我々は、この問題の上下境界を導出するために、非定常対策を両方採用する。
  論文  参考訳（メタデータ） (2022-05-25T01:22:36Z)
• Online Learning with Knapsacks: the Best of Both Worlds [54.28273783164608]
  オンライン学習の課題として,意思決定者が,リソース制約の有限セットに違反することなく,期待する報酬を最大化したい,という課題を提起する。 当社のフレームワークは,意思決定者がそのエビデンスを柔軟かつコスト論的に扱えるようにします。
  論文  参考訳（メタデータ） (2022-02-28T12:10:48Z)
• Universal and data-adaptive algorithms for model selection in linear contextual bandits [52.47796554359261]
  モデル選択の最も単純な非自明な例を考える: 単純な多重武装バンディット問題と線形文脈バンディット問題とを区別する。 データ適応的な方法で探索する新しいアルゴリズムを導入し、$mathcalO(dalpha T1- alpha)$という形式の保証を提供する。 我々のアプローチは、いくつかの仮定の下で、ネストされた線形文脈包帯のモデル選択に拡張する。
  論文  参考訳（メタデータ） (2021-11-08T18:05:35Z)
• Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection [71.9765117768556]
  本研究では,高次元線形モデルの下での文脈的帯域問題について考察する。 この設定は、パーソナライズされたレコメンデーション、オンライン広告、パーソナライズされた医療など、不可欠な応用を見出す。 本稿では,最適部分集合選択法を用いて2重成長エポックを推定する手法を提案する。
  論文  参考訳（メタデータ） (2020-09-04T04:10:39Z)

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

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