論文の概要: Tractable Multinomial Logit Contextual Bandits with Non-Linear Utilities
- arxiv url: http://arxiv.org/abs/2601.06913v1
- Date: Sun, 11 Jan 2026 13:43:42 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-01-13 19:08:01.062922
- Title: Tractable Multinomial Logit Contextual Bandits with Non-Linear Utilities
- Title（参考訳）: 非線形機能を有するトラクタブルマルチノードロジットコンテキストバンド
- Authors: Taehyun Hwang, Dahngoon Kim, Min-hwan Oh,
- Abstract要約: 逐次アソート選択のためのMNL(Multinomial logit)コンテキスト帯域問題について検討する。
提案手法は, 非線形効用を有するMNLコンテキスト帯域に対する, 計算処理可能な最初のアルゴリズムである。
- 参考スコア（独自算出の注目度）: 34.403840521131606
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: We study the multinomial logit (MNL) contextual bandit problem for sequential assortment selection. Although most existing research assumes utility functions to be linear in item features, this linearity assumption restricts the modeling of intricate interactions between items and user preferences. A recent work (Zhang & Luo, 2024) has investigated general utility function classes, yet its method faces fundamental trade-offs between computational tractability and statistical efficiency. To address this limitation, we propose a computationally efficient algorithm for MNL contextual bandits leveraging the upper confidence bound principle, specifically designed for non-linear parametric utility functions, including those modeled by neural networks. Under a realizability assumption and a mild geometric condition on the utility function class, our algorithm achieves a regret bound of $\tilde{O}(\sqrt{T})$, where $T$ denotes the total number of rounds. Our result establishes that sharp $\tilde{O}(\sqrt{T})$-regret is attainable even with neural network-based utilities, without relying on strong assumptions such as neural tangent kernel approximations. To the best of our knowledge, our proposed method is the first computationally tractable algorithm for MNL contextual bandits with non-linear utilities that provably attains $\tilde{O}(\sqrt{T})$ regret. Comprehensive numerical experiments validate the effectiveness of our approach, showing robust performance not only in realizable settings but also in scenarios with model misspecification.
- Abstract（参考訳）: 逐次アソート選択のためのMNL(Multinomial logit)コンテキスト帯域問題について検討する。
多くの既存研究では、ユーティリティ関数はアイテムの特徴において線形であると仮定しているが、この線形性仮定はアイテムとユーザの好みの間の複雑な相互作用のモデリングを制限する。
最近の研究 (Zhang & Luo, 2024) では一般ユーティリティ関数クラスが検討されているが、その手法は計算的トラクタビリティと統計的効率の基本的なトレードオフに直面している。
この制限に対処するために、ニューラルネットワークでモデル化されたものを含む非線形パラメトリックなユーティリティ関数に特化して設計された、高信頼境界原理を利用するMNLコンテキスト帯域に対する計算効率の良いアルゴリズムを提案する。
実用関数クラス上の実現可能性仮定と緩やかな幾何学的条件の下で、我々のアルゴリズムは、$\tilde{O}(\sqrt{T})$の後悔境界を達成し、$T$はラウンドの総数を表す。
我々の結果は、ニューラルネットワークベースのユーティリティでさえ、ニューラルネットワークによるカーネル近似のような強い仮定に頼ることなく、シャープな$\tilde{O}(\sqrt{T})$-regretが達成可能であることを証明している。
我々の知る限り、提案手法は、MNLの文脈的包帯を非線形ユーティリティで計算的に抽出可能な最初のアルゴリズムであり、$\tilde{O}(\sqrt{T})$ regretを確実に達成している。
総合的な数値実験により提案手法の有効性が検証され, 実現可能な設定だけでなく, モデル不特定性のあるシナリオにおいても頑健な性能を示す。
関連論文リスト
- Neural Variance-aware Dueling Bandits with Deep Representation and Shallow Exploration [6.287267171078442]
ニューラルネットワークを利用して非線形ユーティリティ関数を近似する分散認識アルゴリズムを提案する。
十分広いニューラルネットワークに対して,我々のアルゴリズムが次数$bigollt(d sqrtsum_t=1T sigma_t2 + sqrtdTrt)のサブ線形累積平均後悔を達成できることを示す理論的保証を確立する。
論文 参考訳（メタデータ） (2025-06-02T01:58:48Z) - Outcome-Based Online Reinforcement Learning: Algorithms and Fundamental Limits [58.63897489864948]
結果に基づくフィードバックによる強化学習は、根本的な課題に直面します。
適切なアクションにクレジットを割り当てるには?
本稿では,一般関数近似を用いたオンラインRLにおけるこの問題の包括的解析を行う。
論文 参考訳（メタデータ） (2025-05-26T17:44:08Z) - Provably Efficient Neural Offline Reinforcement Learning via Perturbed
Rewards [33.88533898709351]
VIPeRは、ランダム化された値関数のアイデアと悲観主義の原理を一致させる。
オフラインデータを複数回摂動することで、暗黙的に悲観性を得る。
ニューラルネットワーク関数近似を用いた一般的なマルコフ決定過程(MDP)において、証明可能かつ計算的に効率的である。
論文 参考訳（メタデータ） (2023-02-24T17:52:12Z) - Sample-Then-Optimize Batch Neural Thompson Sampling [50.800944138278474]
我々はトンプソンサンプリング(TS)ポリシーに基づくブラックボックス最適化のための2つのアルゴリズムを提案する。
入力クエリを選択するには、NNをトレーニングし、トレーニングされたNNを最大化してクエリを選択するだけです。
我々のアルゴリズムは、大きなパラメータ行列を逆転する必要性を助長するが、TSポリシーの妥当性は保たれている。
論文 参考訳（メタデータ） (2022-10-13T09:01:58Z) - Efficient and Near-Optimal Smoothed Online Learning for Generalized
Linear Functions [28.30744223973527]
我々は,K-wise線形分類において,統計学的に最適なログ(T/sigma)の後悔を初めて楽しむ計算効率のよいアルゴリズムを提案する。
一般化線形分類器によって誘導される不一致領域の幾何学の新たな特徴付けを開発する。
論文 参考訳（メタデータ） (2022-05-25T21:31:36Z) - Minimax Optimal Quantization of Linear Models: Information-Theoretic
Limits and Efficient Algorithms [59.724977092582535]
測定から学習した線形モデルの定量化の問題を考える。
この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。
本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
論文 参考訳（メタデータ） (2022-02-23T02:39:04Z) - Learning Contextual Bandits Through Perturbed Rewards [107.6210145983805]
標準正規性条件下では、$tildeO(tildedsqrtT)$ regret上界が達成可能であることを示す。
明示的な探索の必要性を排除するために、ニューラルネットワークを更新する際の報酬を混乱させます。
論文 参考訳（メタデータ） (2022-01-24T19:10:22Z) - Multinomial Logit Contextual Bandits: Provable Optimality and
Practicality [15.533842336139063]
パラメータが不明な多項式ロギット(MNL)選択モデルによってユーザ選択が与えられる順序選択選択問題を検討する。
本稿では,このMNLコンテクストバンディットに対する高信頼境界に基づくアルゴリズムを提案する。
本稿では,アルゴリズムの単純な変種が,幅広い重要なアプリケーションに対して最適な後悔を与えることを示す。
論文 参考訳（メタデータ） (2021-03-25T15:42:25Z) - What needles do sparse neural networks find in nonlinear haystacks [0.0]
人工ニューラルネットワーク(ANN)におけるスパーシリティ誘導ペナルティは、特にノイズが高く、トレーニングセットが小さい状況において、過度な適合を避ける。
線形モデルの場合、そのようなアプローチは、適切なコセンのペナルティパラメータに対するレギュレーションにおいて高い確率で重要な特徴を確実に回復する。
簡単なモデルを用いてモンテカルロシミュレーションを行い,提案手法の有効性を示した。
論文 参考訳（メタデータ） (2020-06-07T04:46:55Z) - Provably Efficient Safe Exploration via Primal-Dual Policy Optimization [105.7510838453122]
制約付きマルコフ決定過程(CMDP)を用いた安全強化学習(SRL)問題について検討する。
本稿では,関数近似設定において,安全な探索を行うCMDPの効率の良いオンラインポリシー最適化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-03-01T17:47:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。