論文の概要: Improved Optimistic Algorithms for Logistic Bandits

• arxiv url: http://arxiv.org/abs/2002.07530v2
• Date: Mon, 8 Jun 2020 07:36:22 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-30 19:24:08.662313
• Title: Improved Optimistic Algorithms for Logistic Bandits
• Title（参考訳）: ロジスティックバンディットの楽観的アルゴリズムの改善
• Authors: Louis Faury, Marc Abeille, Cl\'ement Calauz\`enes, Olivier Fercoq
• Abstract要約: そこで本稿では,報酬関数の非線形性について,より詳細な検証に基づく新しい楽観的アルゴリズムを提案する。 我々は、$tildemathcalO(sqrtT)$ regretを楽しんでおり、$kappa$に依存しないが、第2の順序の項には依存しないことを示す。
• 参考スコア（独自算出の注目度）: 16.140301473601454
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The generalized linear bandit framework has attracted a lot of attention in recent years by extending the well-understood linear setting and allowing to model richer reward structures. It notably covers the logistic model, widely used when rewards are binary. For logistic bandits, the frequentist regret guarantees of existing algorithms are $\tilde{\mathcal{O}}(\kappa \sqrt{T})$, where $\kappa$ is a problem-dependent constant. Unfortunately, $\kappa$ can be arbitrarily large as it scales exponentially with the size of the decision set. This may lead to significantly loose regret bounds and poor empirical performance. In this work, we study the logistic bandit with a focus on the prohibitive dependencies introduced by $\kappa$. We propose a new optimistic algorithm based on a finer examination of the non-linearities of the reward function. We show that it enjoys a $\tilde{\mathcal{O}}(\sqrt{T})$ regret with no dependency in $\kappa$, but for a second order term. Our analysis is based on a new tail-inequality for self-normalized martingales, of independent interest.
• Abstract（参考訳）: 一般化線形バンディットフレームワークは、よく理解された線形設定を拡張し、よりリッチな報酬構造をモデル化することで、近年多くの注目を集めている。 特に、報酬がバイナリであるときに広く使用されるロジスティックモデルをカバーする。 ロジスティックな盗賊にとって、既存のアルゴリズムの頻繁な後悔の保証は$\tilde{\mathcal{O}}(\kappa \sqrt{T})$であり、$\kappa$は問題依存定数である。 残念ながら、$\kappa$ は決定セットのサイズに指数関数的にスケールするので任意に大きくなる。 これは、非常にゆるやかな後悔と経験的なパフォーマンスをもたらす可能性がある。 本稿では,$\kappa$が導入した禁止的依存関係に着目して,ロジスティックバンディットについて検討する。 本稿では,報奨関数の非線形性を詳細に検討した新しい楽観的アルゴリズムを提案する。 我々は、$\tilde{\mathcal{O}}(\sqrt{T})$ regretを楽しんでおり、$\kappa$に依存せず、二項目の項で表現する。 我々の分析は、独立した関心を持つ自己正規化マリンガレに対する新しい尾不等式に基づいている。

関連論文リスト

• 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)
• Improved Regret Bounds of (Multinomial) Logistic Bandits via Regret-to-Confidence-Set Conversion [40.159846982245746]
  我々は,オンライン学習アルゴリズムのテキストテキシスタンスのみに基づく凸信頼セットを,後悔の保証付きで構築する。 R2CSを用いて、計算実現可能性を維持しながら、ロジスティックな包帯におけるw.r.t.$S$を厳格に改善する。 我々は,この分析を多項ロジスティック・バンディットにまで拡張し,R2CSの有効性を示した。
  論文  参考訳（メタデータ） (2023-10-28T01:27:52Z)
• Improved High-Probability Regret for Adversarial Bandits with Time-Varying Feedback Graphs [62.52390282012508]
  我々は、T$ラウンド以上の時間変化フィードバックグラフを持つ、敵対的な$K$武器付きバンディットに対する高い確率的後悔境界について検討する。 提案アルゴリズムは,高い確率で最適に後悔する$widetildemathcalO((sum_t=1Talpha_t)1/2+max_tin[T]alpha_t]$を達成するアルゴリズムを開発した。 また,弱可観測グラフに対する最適高確率残差を求めるアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-10-04T04:36:15Z)
• Leveraging Initial Hints for Free in Stochastic Linear Bandits [38.58449930961883]
  本研究では,学習者の事前知識を付加した帯域フィードバックによる最適化の設定について,最適行動の最初のヒントとして検討する。 我々は、このヒントを用いて、ヒントが正確である場合にその後悔を$tilde O(sqrtT)$に改善する新しいアルゴリズムを提案する。 おそらく驚くべきことに、私たちの研究は、最悪のパフォーマンスを犠牲にすることなく、ヒントを活用することで、証明可能な利益が得られていることを示している。
  論文  参考訳（メタデータ） (2022-03-08T18:48:55Z)
• An Experimental Design Approach for Regret Minimization in Logistic Bandits [26.674062544226636]
  ロジスティックな盗賊の最大の課題は、潜在的に大きな問題に依存する定数$kappa$への依存を減らすことである。 そこで本研究では,新しいウォームアップサンプリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-02-04T21:56:40Z)
• Instance-Wise Minimax-Optimal Algorithms for Logistic Bandits [9.833844886421694]
  ロジスティック・バンディットは、パラメタライズド・バンディットにおける非線形性の影響を理解するための、散らかったが挑戦的な枠組みを提供することによって、かなりの注目を集めている。 非線型性の効果を精密に解析する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-10-23T20:07:31Z)
• Thresholded Lasso Bandit [70.17389393497125]
  Thresholded Lasso banditは、報酬関数を定義するベクトルとスパースサポートを推定するアルゴリズムである。 一般には $mathcalO( log d + sqrtT )$ や $mathcalO( log d + sqrtT )$ としてスケールする非漸近的後悔の上界を確立する。
  論文  参考訳（メタデータ） (2020-10-22T19:14:37Z)
• Impact of Representation Learning in Linear Bandits [83.17684841392754]
  本研究では,表現学習が帯域幅問題の効率性を向上させる方法について検討する。 我々は,$widetildeO(TsqrtkN + sqrtdkNT)$ regretを達成する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-10-13T16:35:30Z)
• Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon [88.75843804630772]
  エピソード強化学習は文脈的包帯を一般化する。 長期計画の地平線と未知の状態依存的な遷移は、サンプルの複雑さに若干の困難をもたらす。 MVPは$left(sqrtSAK + S2Aright)$ regretを楽しみ、$Omegaleft(sqrtSAK + S2Aright)$ lower bound of emphcontextual bandits to logarithmic termsに近づいている。
  論文  参考訳（メタデータ） (2020-09-28T17:52:32Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)

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

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