論文の概要: Improved Online Confidence Bounds for Multinomial Logistic Bandits

• arxiv url: http://arxiv.org/abs/2502.10020v1
• Date: Fri, 14 Feb 2025 09:01:12 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-17 14:47:45.983253
• Title: Improved Online Confidence Bounds for Multinomial Logistic Bandits
• Title（参考訳）: 多項ロジスティック帯域におけるオンライン信頼境界の改善
• Authors: Joongkyu Lee, Min-hwan Oh,
• Abstract要約: 本稿では,MNLモデルに対するオンライン信頼度の向上を提案する。 この結果をMNLブレイビットに適用し,変分依存性の最適後悔を実現する。
• 参考スコア（独自算出の注目度）: 8.087699764574788
• License:
• Abstract: In this paper, we propose an improved online confidence bound for multinomial logistic (MNL) models and apply this result to MNL bandits, achieving variance-dependent optimal regret. Recently, Lee & Oh (2024) established an online confidence bound for MNL models and achieved nearly minimax-optimal regret in MNL bandits. However, their results still depend on the norm-boundedness of the unknown parameter $B$ and the maximum size of possible outcomes $K$. To address this, we first derive an online confidence bound of $O\left(\sqrt{d \log t} + B \right)$, which is a significant improvement over the previous bound of $O (B \sqrt{d} \log t \log K )$ (Lee & Oh, 2024). This is mainly achieved by establishing tighter self-concordant properties of the MNL loss and introducing a novel intermediary term to bound the estimation error. Using this new online confidence bound, we propose a constant-time algorithm, OFU-MNL++, which achieves a variance-dependent regret bound of $O \Big( d \log T \sqrt{ \smash[b]{\sum_{t=1}^T} \sigma_t^2 } \Big) $ for sufficiently large $T$, where $\sigma_t^2$ denotes the variance of the rewards at round $t$, $d$ is the dimension of the contexts, and $T$ is the total number of rounds. Furthermore, we introduce an Maximum Likelihood Estimation (MLE)-based algorithm that achieves an anytime, OFU-MN$^2$L, poly($(B)$)-free regret of $O \Big( d \log (BT) \sqrt{ \smash[b]{\sum_{t=1}^T} \sigma_t^2 } \Big) $.
• Abstract（参考訳）: 本稿では,多相ロジスティックモデル(MNL)に対するオンライン信頼度の向上を提案し,これをMNLの盗賊に適用し,分散依存的最適後悔を実現する。 最近、Lee & Oh (2024) はMNLモデルのオンライン信頼度を確立し、MNLの盗賊の最小限の後悔をほぼ達成した。 しかし、それらの結果は未知のパラメータのノルム有界性$B$と可能な結果の最大サイズ$K$に依存している。 この問題に対処するために、まずオンライン信頼境界の$O\left(\sqrt{d \log t} + B \right)$を導出し、これは以前の境界の$O (B \sqrt{d} \log t \log K )$ (Lee & Oh, 2024) よりも大幅に改善する。 これは主に、MNL損失のより厳密な自己調和特性を確立し、推定誤差をバウンドする新たな中間項を導入することで達成される。 この新たなオンライン信頼境界を用いて、定数時間アルゴリズム OFU-MNL++ を提案し、$O \Big( d \log T \sqrt{ \smash[b]{\sum_{t=1}^T} \sigma_t^2 } \Big) $ for enough large $T$, ここで、$\sigma_t^2$ はラウンド$t$での報酬の分散を表し、$d$ はコンテキストの次元であり、$T$ はラウンドの総数である。 さらに,O-MN$^2$L,poly($(B)$)-free regret of $O \Big(d \log (BT) \sqrt{ \smash[b]{\sum_{t=1}^T} \sigma_t^2 } \Big) $を任意の時間,OU-MN$^2$L,poly($(B)$)-free regret とするアルゴリズムを導入する。

関連論文リスト

• Nearly Minimax Optimal Regret for Multinomial Logistic Bandit [8.087699764574788]
  本研究では,学習エージェントが文脈情報に基づいて順にアソシエーションを選択する,文脈多項ロジット(MNL)バンディット問題について検討する。 特に最大品位が$K$の場合には、下限と上限の差が顕著である。 定数時間アルゴリズム OFU-MNL+ を提案し, 一致する上限を $tildeO(dsqrtsmash[b]T/K)$ とする。
  論文  参考訳（メタデータ） (2024-05-16T06:07:31Z)
• MNL-Bandit in non-stationary environments [2.7737587389928793]
  我々は,最悪の場合,$tildeOleft(min left sqrtNTL;,; Nfrac13(Delta_inftyK)frac13 Tfrac23 + sqrtNTrightright)$を後悔するアルゴリズムを提案する。 特に、非定常性による推定器に導入されたバイアスの厳密な評価を行い、新しい濃度境界を導出する。
  論文  参考訳（メタデータ） (2023-03-04T21:10:42Z)
• Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes [62.90204655228324]
  我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。 我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
  論文  参考訳（メタデータ） (2022-10-20T21:32:01Z)
• Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPs [111.75736569611159]
  線形混合MDPのための計算効率のよい初めての地平線フリーアルゴリズムを提案する。 我々のアルゴリズムは、未知の遷移力学に対する重み付き最小二乗推定器に適応する。 これにより、$sigma_k2$'sが知られているときに、この設定で最もよく知られたアルゴリズムも改善される。
  論文  参考訳（メタデータ） (2022-05-23T17:59:18Z)
• Nearly Horizon-Free Offline Reinforcement Learning [97.36751930393245]
  S$状態、$A$アクション、計画的地平$H$で、エピソードな時間同質なMarkov決定プロセスに関するオフライン強化学習を再考する。 経験的MDPを用いた評価と計画のための,約$H$自由なサンプル複雑性境界の最初の集合を得る。
  論文  参考訳（メタデータ） (2021-03-25T18:52:17Z)
• Multinomial Logit Contextual Bandits: Provable Optimality and Practicality [15.533842336139063]
  パラメータが不明な多項式ロギット(MNL)選択モデルによってユーザ選択が与えられる順序選択選択問題を検討する。 本稿では,このMNLコンテクストバンディットに対する高信頼境界に基づくアルゴリズムを提案する。 本稿では,アルゴリズムの単純な変種が,幅広い重要なアプリケーションに対して最適な後悔を与えることを示す。
  論文  参考訳（メタデータ） (2021-03-25T15:42:25Z)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  我々は,バンディットフィードバックを用いてオンライン学習を学習する。 learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。 我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。 ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
  論文  参考訳（メタデータ） (2021-02-15T08:16:51Z)
• 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)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)

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

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