論文の概要: Nash Regret Guarantees for Linear Bandits

• arxiv url: http://arxiv.org/abs/2310.02023v1
• Date: Tue, 3 Oct 2023 12:58:10 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-04 14:19:22.947124
• Title: Nash Regret Guarantees for Linear Bandits
• Title（参考訳）: 線形バンディットに対するナッシュ後悔の保証
• Authors: Ayush Sawarni, Soumybrata Pal, and Siddharth Barman
• Abstract要約: 我々は,Nashが$Oleft(sqrtfracdnuT log(T |X|)right)$を後悔するアルゴリズムを開発した。 さらに、アームの集合 X$ が必ずしも有限ではない線形バンドイットのインスタンスに対処すると、ナッシュ後悔の上限 $Oleft( fracdfrac54nufrac12sqrtT log(T)right)$ が得られる。
• 参考スコア（独自算出の注目度）: 12.494184403263338
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We obtain essentially tight upper bounds for a strengthened notion of regret in the stochastic linear bandits framework. The strengthening -- referred to as Nash regret -- is defined as the difference between the (a priori unknown) optimum and the geometric mean of expected rewards accumulated by the linear bandit algorithm. Since the geometric mean corresponds to the well-studied Nash social welfare (NSW) function, this formulation quantifies the performance of a bandit algorithm as the collective welfare it generates across rounds. NSW is known to satisfy fairness axioms and, hence, an upper bound on Nash regret provides a principled fairness guarantee. We consider the stochastic linear bandits problem over a horizon of $T$ rounds and with set of arms ${X}$ in ambient dimension $d$. Furthermore, we focus on settings in which the stochastic reward -- associated with each arm in ${X}$ -- is a non-negative, $\nu$-sub-Poisson random variable. For this setting, we develop an algorithm that achieves a Nash regret of $O\left( \sqrt{\frac{d\nu}{T}} \log( T |X|)\right)$. In addition, addressing linear bandit instances in which the set of arms ${X}$ is not necessarily finite, we obtain a Nash regret upper bound of $O\left( \frac{d^\frac{5}{4}\nu^{\frac{1}{2}}}{\sqrt{T}} \log(T)\right)$. Since bounded random variables are sub-Poisson, these results hold for bounded, positive rewards. Our linear bandit algorithm is built upon the successive elimination method with novel technical insights, including tailored concentration bounds and the use of sampling via John ellipsoid in conjunction with the Kiefer-Wolfowitz optimal design.
• Abstract（参考訳）: 確率的線形バンディットの枠組みにおける後悔の強固な概念に対する本質的に強固な上界を得る。 Nash regret と呼ばれる強化は、(事前未知の)最適化と線形バンドイットアルゴリズムによって蓄積される期待報酬の幾何学的平均との差として定義される。 幾何学的平均はよく研究されたナッシュ社会福祉(nsw)関数に対応するため、この定式化はバンディットアルゴリズムの性能をラウンドをまたいだ集団的福祉として定量化する。 NSW はフェアネス公理を満たすことが知られており、ナッシュの後悔の上限は原理化されたフェアネスを保証する。 我々は、T$の水平線上の確率線型包帯問題と、周囲次元$d$における腕の組${X}$を考える。 さらに、${X}$ の各アームに付随する確率的報酬が非負の $\nu$-sub-Poisson 確率変数であるような設定に焦点を当てる。 この設定のために、Nashが$O\left( \sqrt {\frac{d\nu}{T}} \log(T |X|)\right)$を後悔するアルゴリズムを開発する。 さらに、腕の集合{X}$が必ずしも有限でない線型バンドイットのインスタンスに対処すると、ナッシュ後悔の上界は$O\left( \frac{d^\frac{5}{4}\nu^{\frac{1}{2}}}{\sqrt{T}} \log(T)\right)$となる。 有界確率変数は部分ポアソンであるため、これらの結果は有界で正の報酬を持つ。 線形バンドイットアルゴリズムは,Keefer-Wolfowitz最適設計と連動して,調整された濃度境界やJohn ellipsoid を用いたサンプリングなど,新しい技術的洞察を持つ逐次除去法に基づいて構築されている。

関連論文リスト

• 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)
• Communication-Constrained Bandits under Additive Gaussian Noise [111.06688156723018]
  クライアントが学習者にコミュニケーション制約のあるフィードバックを提供する分散マルチアームバンディットについて検討する。 我々は、この下限を小さな加法係数にマッチさせるマルチフェーズ帯域幅アルゴリズム、$mathtUEtext-UCB++$を提案する。
  論文  参考訳（メタデータ） (2023-04-25T09:31:20Z)
• Fairness and Welfare Quantification for Regret in Multi-Armed Bandits [13.094997642327371]
  我々は後悔という概念を反逆主義者の視点で拡張する。 我々はナッシュの後悔について研究し、前兆不明の最適平均(腕の間)とアルゴリズムのパフォーマンスの違いとして定義する。
  論文  参考訳（メタデータ） (2022-05-27T12:12:56Z)
• Nearly Minimax Algorithms for Linear Bandits with Shared Representation [86.79657561369397]
  我々は、次元が$d$で、それぞれ$T$のラウンドで$M$リニアバンディットをプレイする設定を考え、これらの$M$リニアバンディットタスクは共通の$k(ll d)$次元リニア表現を共有する。 我々は$widetildeOleft(dsqrtkMT + kMsqrtTright)$ regret boundsを達成する新しいアルゴリズムを考案した。
  論文  参考訳（メタデータ） (2022-03-29T15:27:13Z)
• Adversarial Combinatorial Bandits with General Non-linear Reward Functions [29.775097827244853]
  既知の非線形報酬関数を用いて対向性バンディットを研究し、対向性線形バンディットに関する既存の研究を延長する。 我々は、$N$の腕と$K$の腕のサブセットが$T$の期間のそれぞれで選択されている場合、ミニマックスの最適な後悔は$widetildeTheta_d(Nd T)$報酬関数が$dK$の$d$度であり、$ta_K(sqrtK T)$報酬関数が低度ではない場合です。
  論文  参考訳（メタデータ） (2021-01-05T00:56:27Z)
• Impact of Representation Learning in Linear Bandits [83.17684841392754]
  本研究では,表現学習が帯域幅問題の効率性を向上させる方法について検討する。 我々は,$widetildeO(TsqrtkN + sqrtdkNT)$ regretを達成する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-10-13T16:35:30Z)
• 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)
• Regret and Belief Complexity Trade-off in Gaussian Process Bandits via Information Thresholding [42.669970064867556]
  GPバンディットアルゴリズムの残差境界と後部分布の複雑さのトレードオフを特徴付ける方法を示す。 大域的最適化に応用したGPバンディットアルゴリズムの精度と複雑性のトレードオフを観察する。
  論文  参考訳（メタデータ） (2020-03-23T21:05:15Z)

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

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