論文の概要: Budget-Constrained Bandits over General Cost and Reward Distributions

• arxiv url: http://arxiv.org/abs/2003.00365v1
• Date: Sat, 29 Feb 2020 23:50:08 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-27 20:16:36.792047
• Title: Budget-Constrained Bandits over General Cost and Reward Distributions
• Title（参考訳）: 一般費用及びリワード分布に対する予算制約帯域
• Authors: Semih Cayci, Atilla Eryilmaz, R. Srikant
• Abstract要約: 我々は,各アームがランダムなコストを発生させ,その見返りにランダムな報酬を与える,予算制約付きバンディット問題を考える。 ある$gamma > 0$ に対して位数 $(2+gamma)$ のモーメントが存在するならば、$O(log B)$ regret は予算 $B>0$ に対して達成可能である。
• 参考スコア（独自算出の注目度）: 32.63624728528415
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider a budget-constrained bandit problem where each arm pull incurs a random cost, and yields a random reward in return. The objective is to maximize the total expected reward under a budget constraint on the total cost. The model is general in the sense that it allows correlated and potentially heavy-tailed cost-reward pairs that can take on negative values as required by many applications. We show that if moments of order $(2+\gamma)$ for some $\gamma > 0$ exist for all cost-reward pairs, $O(\log B)$ regret is achievable for a budget $B>0$. In order to achieve tight regret bounds, we propose algorithms that exploit the correlation between the cost and reward of each arm by extracting the common information via linear minimum mean-square error estimation. We prove a regret lower bound for this problem, and show that the proposed algorithms achieve tight problem-dependent regret bounds, which are optimal up to a universal constant factor in the case of jointly Gaussian cost and reward pairs.
• Abstract（参考訳）: 我々は,各アームプルがランダムなコストを伴い,見返りにランダムな報酬を与える予算制約付きバンディット問題を考える。 目標は、総コストに対する予算制約の下で、期待される総報酬を最大化することである。 このモデルは、多くのアプリケーションで要求される負の値を取ることができる相関的かつ潜在的に重み付きコスト-リワード対を許容するという意味で一般的なものである。 ある$\gamma > 0$ に対して位数 $(2+\gamma)$ のモーメントが存在するならば、$O(\log B)$ regret は予算 $B>0$ に対して達成可能であることを示す。 そこで本研究では,線形最小平均二乗誤差推定による共通情報を抽出し,各アームのコストと報酬の相関を生かすアルゴリズムを提案する。 我々は,この問題に対する後悔の少ない境界を証明し,提案したアルゴリズムが,ガウスコストと報酬対の場合の普遍的定数係数に最適である厳密な問題依存の後悔境界を達成することを示す。

関連論文リスト

• A General Framework for Clustering and Distribution Matching with Bandit Feedback [81.50716021326194]
  我々は,帯域幅フィードバックを用いたクラスタリングと分散マッチング問題のための一般的なフレームワークを開発する。 誤り確率が$delta$を超えない任意のオンラインアルゴリズムに対して、平均アームプル数に基づいて漸近的でない下界を導出する。
  論文  参考訳（メタデータ） (2024-09-08T12:19:12Z)
• Pure Exploration for Constrained Best Mixed Arm Identification with a Fixed Budget [6.22018632187078]
  固定予算の制約付きベスト・ミックスアーム識別(CBMAI)問題を導入する。 目標は、与えられた学習予算$N$で、期待されるコストの制約によって期待される報酬を最大化する最高の混合アームを見つけることである。 我々は、(最良の混合アームの支持の)誤識別に関する理論上の上限を提供し、予算$N$で指数関数的に崩壊することを示す。
  論文  参考訳（メタデータ） (2024-05-23T22:35:11Z)
• Confounded Budgeted Causal Bandits [28.199741662190203]
  基礎となる因果グラフをモデルとした環境における「良い」介入の学習問題について検討する。 良い介入は報酬を最大化する介入を指す。 一般因果グラフにおける累積後悔を最小限に抑えるアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-01-15T10:26:13Z)
• Small Total-Cost Constraints in Contextual Bandits with Knapsacks, with Application to Fairness [1.6741394365746018]
  我々は,各ラウンドにおいてスカラー報酬が得られ,ベクトル値のコストがかかる問題であるknapsacks[CBwK]のコンテキスト的帯域幅問題を考える。 予測段階更新に基づく二元的戦略を導入し,多元対数項まで$sqrtT$の総コスト制約を扱えるようにした。
  論文  参考訳（メタデータ） (2023-05-25T07:41:35Z)
• Double Doubly Robust Thompson Sampling for Generalized Linear Contextual Bandits [8.508198765617198]
  一般化線形報酬に$tildeO(sqrtkappa-1 phi T)$ regret over $T$ roundsを提案する。 また、確率的マージン条件下では、$O(kappa-1 phi log (NT) log T)$ regret bound for $N$ arms も提供する。
  論文  参考訳（メタデータ） (2022-09-15T00:20:38Z)
• Causal Bandits for Linear Structural Equation Models [58.2875460517691]
  本稿では,因果図形モデルにおける最適な介入順序を設計する問題について検討する。 グラフの構造は知られており、ノードは$N$である。 頻繁性(UCBベース)とベイズ的設定に2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-08-26T16:21:31Z)
• A Lyapunov-Based Methodology for Constrained Optimization with Bandit Feedback [22.17503016665027]
  各アクションが未知の関節分布からランダムな報酬、コスト、ペナルティを返す問題を考える。 我々は、$tt LyOn$という新しい低複雑さアルゴリズムを提案し、$O(sqrtBlog B)$ regretと$O(log B/B)$ constraint-violationを達成することを証明した。 計算コストの低い$tt LyOn$は、Lyapunovをベースとしたアルゴリズム設計手法が制約付き帯域最適化問題の解決に有効であることを示唆している。
  論文  参考訳（メタデータ） (2021-06-09T16:12:07Z)
• Combinatorial Bandits without Total Order for Arms [52.93972547896022]
  セット依存報酬分布を捕捉し、武器の合計順序を仮定しない報酬モデルを提案する。 我々は、新しい後悔分析を開発し、$Oleft(frack2 n log Tepsilonright)$ gap-dependent regret boundと$Oleft(k2sqrtn T log Tright)$ gap-dependent regret boundを示す。
  論文  参考訳（メタデータ） (2021-03-03T23:08:59Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。 一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-20T04:29:18Z)
• 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)

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

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