論文の概要: Chained Information-Theoretic bounds and Tight Regret Rate for Linear Bandit Problems

• arxiv url: http://arxiv.org/abs/2403.03361v1
• Date: Tue, 5 Mar 2024 23:08:18 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-07 16:45:33.256740
• Title: Chained Information-Theoretic bounds and Tight Regret Rate for Linear Bandit Problems
• Title（参考訳）: 線形帯域問題に対する連鎖情報理論境界とタイト回帰率
• Authors: Amaury Gouverneur, Borja Rodr\'iguez-G\'alvez, Tobias J. Oechtering, Mikael Skoglund
• Abstract要約: バンドイット問題に対するトンプソン・サンプリングアルゴリズムの変形に対する後悔について検討する。 報酬の適切な連続性仮定の下で、我々の境界は、$d$次元線形バンディット問題に対して$O(dsqrtT)$の厳密なレートを提供する。
• 参考スコア（独自算出の注目度）: 37.82763068378491
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper studies the Bayesian regret of a variant of the Thompson-Sampling algorithm for bandit problems. It builds upon the information-theoretic framework of [Russo and Van Roy, 2015] and, more specifically, on the rate-distortion analysis from [Dong and Van Roy, 2020], where they proved a bound with regret rate of $O(d\sqrt{T \log(T)})$ for the $d$-dimensional linear bandit setting. We focus on bandit problems with a metric action space and, using a chaining argument, we establish new bounds that depend on the metric entropy of the action space for a variant of Thompson-Sampling. Under suitable continuity assumption of the rewards, our bound offers a tight rate of $O(d\sqrt{T})$ for $d$-dimensional linear bandit problems.
• Abstract（参考訳）: 本稿では,バンディット問題に対するトンプソンサンプリングアルゴリズムの変種について,ベイズ的後悔について述べる。 これは [russo and van roy, 2015] の情報理論の枠組みと, [dong and van roy, 2020] からのレート・ディストリクト解析に基づいて構築され,d$-dimensional linear bandit 設定に対して $o(d\sqrt{t \log(t)})$ の後悔率で縛られていることが証明された。 我々は、計量作用空間のバンドイト問題に焦点をあて、連鎖論法を用いて、トンプソン・サンプリングの変種に対する作用空間の計量エントロピーに依存する新しい境界を確立する。 報酬の適切な連続性仮定の下で、我々は$O(d\sqrt{T})$を$d$次元線形バンディット問題に対して厳密なレートで提供する。

関連論文リスト

• Feel-Good Thompson Sampling for Contextual Dueling Bandits [49.450050682705026]
  FGTS.CDBという名前のトンプソンサンプリングアルゴリズムを提案する。 われわれのアルゴリズムの核心は、デュエルバンディットに適した新しいFeel-Good探索用語である。 我々のアルゴリズムは最小限の誤差、すなわち $tildemathcalO(dsqrt T)$, $d$ はモデル次元、$T$ は時間水平線である。
  論文  参考訳（メタデータ） (2024-04-09T04:45:18Z)
• Contexts can be Cheap: Solving Stochastic Contextual Bandits with Linear Bandit Algorithms [39.70492757288025]
  我々は,意思決定者がコンテキストを提供するコンテキスト線形帯域問題に対処する。 文脈問題を線形バンディット問題として解くことができることを示す。 この結果から,文脈的線形包帯に対して$O(dsqrtTlog T)$高確率残差が生じることが示唆された。
  論文  参考訳（メタデータ） (2022-11-08T22:18:53Z)
• Squeeze All: Novel Estimator and Self-Normalized Bound for Linear Contextual Bandits [18.971564419292893]
  我々は、$O(sqrtdTlog T)$ regret boundで、$d$は文脈の次元、$T$は時間地平線であるような線形文脈的帯域幅アルゴリズムを提案する。 提案アルゴリズムは,探索を明示的ランダム化により埋め込んだ新しい推定器を備える。
  論文  参考訳（メタデータ） (2022-06-11T02:43:17Z)
• Breaking the $\sqrt{T}$ Barrier: Instance-Independent Logarithmic Regret in Stochastic Contextual Linear Bandits [10.127456032874978]
  線形ペイオフを伴う文脈的包帯に対する対数的後悔(多元的後悔)を証明した。 コンテキストは、$sqrtT$から$polylog(T)$への後悔を減らすのに役立ちます。
  論文  参考訳（メタデータ） (2022-05-19T23:41:46Z)
• Complete Policy Regret Bounds for Tallying Bandits [51.039677652803675]
  政策後悔は、適応的な敵に対してオンライン学習アルゴリズムのパフォーマンスを測定するという、よく確立された概念である。 我々は,不完全な政策後悔を効果的に最小化できる敵の制限について検討する。 我々は、$tildemathcalO(mKsqrtT)$の完全なポリシーを後悔するアルゴリズムを提供し、$tildemathcalO$表記は対数要素だけを隠す。
  論文  参考訳（メタデータ） (2022-04-24T03:10:27Z)
• 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)
• Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection [71.9765117768556]
  本研究では,高次元線形モデルの下での文脈的帯域問題について考察する。 この設定は、パーソナライズされたレコメンデーション、オンライン広告、パーソナライズされた医療など、不可欠な応用を見出す。 本稿では,最適部分集合選択法を用いて2重成長エポックを推定する手法を提案する。
  論文  参考訳（メタデータ） (2020-09-04T04:10:39Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)
• Contextual Blocking Bandits [35.235375147227124]
  我々は,多腕バンディット問題の新たな変種について検討し,各ステップごとに,腕の平均報酬を決定する独立したサンプルコンテキストをプレイヤーが観察する。 アームを再生することで(すべてのコンテキストにわたって)将来の時間ステップの固定および既知の回数をブロックする。 我々は、$mathcalO(log T)$-regret w.r.t.$alpha$regret戦略を$Tタイムステップで保証し、$Omega(log(T)$low boundと一致する UCB ベースのフル情報アルゴリズムの変種を提案する。
  論文  参考訳（メタデータ） (2020-03-06T20:34:42Z)

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

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