論文の概要: Sparsity-Agnostic Linear Bandits with Adaptive Adversaries

• arxiv url: http://arxiv.org/abs/2406.01192v1
• Date: Mon, 3 Jun 2024 10:54:58 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-06 01:28:45.132105
• Title: Sparsity-Agnostic Linear Bandits with Adaptive Adversaries
• Title（参考訳）: アダプティブ・アダプティブ・アダプティブ・アダプティブ・リニア・バンド
• Authors: Tianyuan Jin, Kyoungseok Jang, Nicolò Cesa-Bianchi,
• Abstract要約: 本研究では,各ラウンドにおいて,学習者が要素を選択して報酬を得る一連の行動(特徴ベクトル)を受信する線形帯域について検討する。 期待される報酬は、選択されたアクションの固定だが未知の線形関数である。 線形報酬関数の非ゼロ係数数$S$に依存するスパース後悔境界について検討する。
• 参考スコア（独自算出の注目度）: 19.84322270472381
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study stochastic linear bandits where, in each round, the learner receives a set of actions (i.e., feature vectors), from which it chooses an element and obtains a stochastic reward. The expected reward is a fixed but unknown linear function of the chosen action. We study sparse regret bounds, that depend on the number $S$ of non-zero coefficients in the linear reward function. Previous works focused on the case where $S$ is known, or the action sets satisfy additional assumptions. In this work, we obtain the first sparse regret bounds that hold when $S$ is unknown and the action sets are adversarially generated. Our techniques combine online to confidence set conversions with a novel randomized model selection approach over a hierarchy of nested confidence sets. When $S$ is known, our analysis recovers state-of-the-art bounds for adversarial action sets. We also show that a variant of our approach, using Exp3 to dynamically select the confidence sets, can be used to improve the empirical performance of stochastic linear bandits while enjoying a regret bound with optimal dependence on the time horizon.
• Abstract（参考訳）: 本研究では,各ラウンドで学習者が一組のアクション(特徴ベクトル)を受け取り,その要素を選択し,確率的報酬を得る確率的線形包帯について検討する。 期待される報酬は、選択されたアクションの固定だが未知の線形関数である。 線形報酬関数の非ゼロ係数数$S$に依存するスパース後悔境界について検討する。 以前の作業は、$S$が知られている場合、またはアクションセットが追加の仮定を満たす場合に焦点を当てていた。 本研究では、S$が未知で作用集合が逆生成されたときに保持される最初のスパース後悔境界を得る。 我々の手法は、オンラインから信頼セットへの変換と、ネストされた信頼セットの階層上の新しいランダム化モデル選択アプローチを組み合わせる。 S$が知られているとき、我々の分析は、逆作用集合の最先端境界を回復する。 また,我々の手法の変種であるExp3を用いて動的に信頼集合を選択することにより,確率線形帯域の経験的性能を向上し,時間的地平線への最適依存に縛られた後悔を享受できることを示す。

関連論文リスト

• Restless Bandit Problem with Rewards Generated by a Linear Gaussian Dynamical System [0.0]
  不確実性の下での意思決定は、頻繁に遭遇する基本的な問題であり、多重武装バンディット問題として定式化することができる。 本稿では,前述した報奨を線形に組み合わせて各アクションの次の報奨を予測する手法を提案する。 選択された前のアクションのシーケンスにかかわらず、事前に選択されたアクションに対してサンプリングされた報酬が、他のアクションの将来の報酬を予測するために使用できることを示す。
  論文  参考訳（メタデータ） (2024-05-15T05:33:49Z)
• 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)
• Linear Bandits with Memory: from Rotting to Rising [5.5969337839476765]
  推奨における飽和効果のような非定常現象は、主に有限個の腕を持つ包帯を用いてモデル化されている。 固定サイズウィンドウにおける学習者の過去の行動の影響を受けない,非定常線形バンディットモデルを提案する。
  論文  参考訳（メタデータ） (2023-02-16T15:02:07Z)
• PopArt: Efficient Sparse Regression and Experimental Design for Optimal Sparse Linear Bandits [29.097522376094624]
  そこで我々はPopArtと呼ばれる単純で効率的なスパース線形推定法を提案する。 我々は, 粗い線形バンディットアルゴリズムを導出し, 美術品の状態に対する後悔の上界の改善を享受する。
  論文  参考訳（メタデータ） (2022-10-25T19:13:20Z)
• A New Look at Dynamic Regret for Non-Stationary Stochastic Bandits [11.918230810566945]
  本研究では,学習過程において各腕の報酬統計が数回変化しうる非定常的マルチアームバンディット問題について検討する。 我々は、$K$の武器付きバンディット問題において、ほぼ最適の$widetilde O(sqrtK N(S+1))$ dynamic regretを実現する方法を提案する。
  論文  参考訳（メタデータ） (2022-01-17T17:23:56Z)
• Top $K$ Ranking for Multi-Armed Bandit with Noisy Evaluations [102.32996053572144]
  我々は,各ラウンドの開始時に,学習者が各アームの真の報酬について,ノイズのない独立した評価を受けるマルチアームバンディット・セッティングを考える。 評価の方法によって異なるアルゴリズムアプローチと理論的保証を導出する。
  論文  参考訳（メタデータ） (2021-12-13T09:48:54Z)
• Anti-Concentrated Confidence Bonuses for Scalable Exploration [57.91943847134011]
  固有の報酬は、探検と探検のトレードオフを扱う上で中心的な役割を果たす。 楕円ボーナスを効率的に近似するためのエンファンティ集中型信頼境界を導入する。 我々は,Atariベンチマーク上での現代固有の報酬と競合する,深層強化学習のための実用的な変種を開発する。
  論文  参考訳（メタデータ） (2021-10-21T15:25:15Z)
• Online Markov Decision Processes with Aggregate Bandit Feedback [74.85532145498742]
  本稿では,オンライン有限水平マルコフ決定過程の新たな変種について検討する。 各エピソードにおいて、学習者は、エピソードの選択した方針によって実現された軌道に沿って蓄積された損失を被り、総括的盗聴フィードバックを観察する。 我々の主な結果は計算効率のよいアルゴリズムで、$O(sqrtK)$ regret for this set, where $K$ is the number of episodes。
  論文  参考訳（メタデータ） (2021-01-31T16:49:07Z)
• 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)

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

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