論文の概要: Enjoying Non-linearity in Multinomial Logistic Bandits

• arxiv url: http://arxiv.org/abs/2507.05306v1
• Date: Mon, 07 Jul 2025 08:18:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-09 16:34:37.255375
• Title: Enjoying Non-linearity in Multinomial Logistic Bandits
• Title（参考訳）: 多項ロジスティックバンドにおける非線形性への期待
• Authors: Pierre Boudart, Pierre Gaillard, Alessandro Rudi,
• Abstract要約: 我々は,学習者が環境と対話する一般化線形帯域幅の変種である多項ロジスティック帯域幅問題を考察する。 我々は、$kappa_*$の定義を多項集合に拡張し、問題の非線形性を活用する効率的なアルゴリズムを提案する。 我々のメソッドは、代入$ smashwidetildemathcalO(Kd sqrtT/kappa_*) $, $K$はアクションの数で、$kappa_*
• 参考スコア（独自算出の注目度）: 66.36004256710824
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the multinomial logistic bandit problem, a variant of generalized linear bandits where a learner interacts with an environment by selecting actions to maximize expected rewards based on probabilistic feedback from multiple possible outcomes. In the binary setting, recent work has focused on understanding the impact of the non-linearity of the logistic model (Faury et al., 2020; Abeille et al., 2021). They introduced a problem-dependent constant $\kappa_*$, that may be exponentially large in some problem parameters and which is captured by the derivative of the sigmoid function. It encapsulates the non-linearity and improves existing regret guarantees over $T$ rounds from $\smash{O(d\sqrt{T})}$ to $\smash{O(d\sqrt{T/\kappa_*})}$, where $d$ is the dimension of the parameter space. We extend their analysis to the multinomial logistic bandit framework, making it suitable for complex applications with more than two choices, such as reinforcement learning or recommender systems. To achieve this, we extend the definition of $\kappa_*$ to the multinomial setting and propose an efficient algorithm that leverages the problem's non-linearity. Our method yields a problem-dependent regret bound of order $ \smash{\widetilde{\mathcal{O}}( Kd \sqrt{{T}/{\kappa_*}})} $, where $K$ is the number of actions and $\kappa_* \ge 1$. This improves upon the best existing guarantees of order $ \smash{\widetilde{\mathcal{O}}( Kd \sqrt{T} )} $. Moreover, we provide a $\smash{ \Omega(d\sqrt{T/\kappa_*})}$ lower-bound, showing that our dependence on $\kappa_*$ is optimal.
• Abstract（参考訳）: 我々は、学習者が複数の可能な結果からの確率的フィードバックに基づいて期待される報酬を最大化するために行動を選択することで環境と相互作用する一般化線形帯域幅の変種である多項ロジスティック帯域幅問題を考察する。 二項式では、最近の研究はロジスティックモデルの非線形性の影響を理解することに重点を置いている(Faury et al , 2020; Abeille et al , 2021)。 彼らは問題依存定数 $\kappa_*$ を導入し、これはいくつかの問題パラメータにおいて指数関数的に大きくなり、シグモイド関数の微分によって捕捉される。 非線型性をカプセル化し、$\smash{O(d\sqrt{T})}$から$\smash{O(d\sqrt{T/\kappa_*})}$への$T$ラウンドに対する既存の後悔の保証を改善する。 我々は、それらの分析を多項ロジスティックバンディットフレームワークに拡張し、強化学習やレコメンダシステムなど、2つ以上の選択肢を持つ複雑なアプリケーションに適合させる。 これを実現するために、$\kappa_*$の定義を多項集合に拡張し、問題の非線形性を活用する効率的なアルゴリズムを提案する。 ここで、K$はアクションの数であり、$\kappa_* \ge 1$である。 これにより、オーダー $ \smash{\widetilde{\mathcal{O}}(Kd \sqrt{T} )} $ の最高の保証が改善される。 さらに、$\smash{ \Omega(d\sqrt{T/\kappa_*})}$low-boundを提供し、$\kappa_*$への依存が最適であることを示す。

関連論文リスト

• Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under $(L_0, L_1)$-Smoothness [74.18546828528298]
  SignSGD with Majority Votingは,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappaka ppakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa -1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappappapa-1right,Kappaを用いて,複雑性の全範囲で堅牢に動作することを示す。
  論文  参考訳（メタデータ） (2025-02-11T19:54:11Z)
• Provably Efficient Reinforcement Learning with Multinomial Logit Function Approximation [67.8414514524356]
  本稿では,MNL関数近似を用いたMDPの新たなクラスについて検討し,状態空間上の確率分布の正当性を保証する。 その大きな利点にもかかわらず、非線形関数を組み込むことは、統計的および計算効率の両方において重大な課題を提起する。 我々は,$widetildemathcalO(dH2sqrtK + kappa-1d2H2)$を後悔するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-05-27T11:31:54Z)
• Best-of-Both-Worlds Algorithms for Linear Contextual Bandits [11.94312915280916]
  両世界のベスト・オブ・ワールドズ・アルゴリズムを$K$武器付き線形文脈包帯に対して検討する。 我々のアルゴリズムは、敵対的体制と敵対的体制の両方において、ほぼ最適の後悔の限界を提供する。
  論文  参考訳（メタデータ） (2023-12-24T08:27:30Z)
• Smoothed Analysis with Adaptive Adversaries [28.940767013349408]
  オンライン問題に対する新しいアルゴリズムの保証を平滑化解析モデルで証明する。 このモデルでは、敵は各時間に一様分布の$tfrac1sigma$倍の密度関数を持つ入力分布を選択する。 本研究の結果は,アルゴリズムの決定と前回の時間ステップにおける入力の実現に基づいて,入力分布を選択可能な適応的敵に対して成り立っている。
  論文  参考訳（メタデータ） (2021-02-16T20:54:49Z)
• Variance-Aware Confidence Set: Variance-Dependent Bound for Linear Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
  線形バンドイットと線形混合決定プロセス(mdp)に対する分散認識信頼セットの構築方法を示す。 線形バンドイットに対しては、$d を特徴次元とする$widetildeo(mathrmpoly(d)sqrt1 + sum_i=1ksigma_i2) が成り立つ。 線形混合 MDP に対し、$widetildeO(mathrmpoly(d)sqrtK)$ regret bound を得る。
  論文  参考訳（メタデータ） (2021-01-29T18:57:52Z)
• Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
  我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。 最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
  論文  参考訳（メタデータ） (2020-03-04T07:36:38Z)
• Improved Optimistic Algorithms for Logistic Bandits [16.140301473601454]
  そこで本稿では,報酬関数の非線形性について,より詳細な検証に基づく新しい楽観的アルゴリズムを提案する。 我々は、$tildemathcalO(sqrtT)$ regretを楽しんでおり、$kappa$に依存しないが、第2の順序の項には依存しないことを示す。
  論文  参考訳（メタデータ） (2020-02-18T12:52:32Z)
• Naive Exploration is Optimal for Online LQR [49.681825576239355]
  最適後悔尺度は$widetildeTheta(sqrtd_mathbfu2 d_mathbfx T)$で、$T$は時間ステップの数、$d_mathbfu$は入力空間の次元、$d_mathbfx$はシステム状態の次元である。 我々の下界は、かつての$mathrmpoly(logT)$-regretアルゴリズムの可能性を排除する。
  論文  参考訳（メタデータ） (2020-01-27T03:44:54Z)

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

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