論文の概要: Multinomial Logit Contextual Bandits: Provable Optimality and Practicality

• arxiv url: http://arxiv.org/abs/2103.13929v1
• Date: Thu, 25 Mar 2021 15:42:25 GMT
• ステータス: 処理完了
• システム内更新日: 2021-03-26 13:51:28.932106
• Title: Multinomial Logit Contextual Bandits: Provable Optimality and Practicality
• Title（参考訳）: 多項ロジットコンテキスト帯域:確率的最適性と実用性
• Authors: Min-hwan Oh, Garud Iyengar
• Abstract要約: パラメータが不明な多項式ロギット(MNL)選択モデルによってユーザ選択が与えられる順序選択選択問題を検討する。 本稿では,このMNLコンテクストバンディットに対する高信頼境界に基づくアルゴリズムを提案する。 本稿では,アルゴリズムの単純な変種が,幅広い重要なアプリケーションに対して最適な後悔を与えることを示す。
• 参考スコア（独自算出の注目度）: 15.533842336139063
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We consider a sequential assortment selection problem where the user choice is given by a multinomial logit (MNL) choice model whose parameters are unknown. In each period, the learning agent observes a $d$-dimensional contextual information about the user and the $N$ available items, and offers an assortment of size $K$ to the user, and observes the bandit feedback of the item chosen from the assortment. We propose upper confidence bound based algorithms for this MNL contextual bandit. The first algorithm is a simple and practical method which achieves an $\tilde{\mathcal{O}}(d\sqrt{T})$ regret over $T$ rounds. Next, we propose a second algorithm which achieves a $\tilde{\mathcal{O}}(\sqrt{dT})$ regret. This matches the lower bound for the MNL bandit problem, up to logarithmic terms, and improves on the best known result by a $\sqrt{d}$ factor. To establish this sharper regret bound, we present a non-asymptotic confidence bound for the maximum likelihood estimator of the MNL model that may be of independent interest as its own theoretical contribution. We then revisit the simpler, significantly more practical, first algorithm and show that a simple variant of the algorithm achieves the optimal regret for a broad class of important applications.
• Abstract（参考訳）: パラメータが不明なマルチノードロジット選択モデル(MNL)によってユーザ選択が与えられる逐次アソート選択問題を考える。 各期間において、学習エージェントは、ユーザに関する$d$−dのコンテキスト情報と、利用可能な$n$のアイテムを観察し、ユーザに対して、サイズ$k$のソートを提供し、ソートから選択したアイテムのバンディットフィードバックを観察する。 本稿では,このMNLコンテキスト帯域に対する高信頼境界ベースアルゴリズムを提案する。 最初のアルゴリズムは単純で実用的な手法で、$t$のラウンドに対して$\tilde{\mathcal{o}}(d\sqrt{t})$を後悔する。 次に, $\tilde{\mathcal{O}}(\sqrt{dT})$ regret を達成する2番目のアルゴリズムを提案する。 これはMNLのバンドイト問題に対する下界と対数項まで一致し、最もよく知られた結果は$\sqrt{d}$ factorによって改善される。 このよりシャープな後悔境界を確立するために、MNLモデルの最大極大推定値に対する漸近的でない信頼度を示す。 次に、より単純でより実用的な第1のアルゴリズムを再検討し、アルゴリズムの単純な変種が、幅広い重要なアプリケーションに最適な後悔をもたらすことを示す。

関連論文リスト

• Nearly Minimax Optimal Regret for Multinomial Logistic Bandit [8.087699764574788]
  本研究では,学習エージェントが文脈情報に基づいて順にアソシエーションを選択する,文脈多項ロジット(MNL)バンディット問題について検討する。 特に最大品位が$K$の場合には、下限と上限の差が顕著である。 定数時間アルゴリズム OFU-MNL+ を提案し, 一致する上限を $tildeO(dsqrtsmash[b]T/K)$ とする。
  論文  参考訳（メタデータ） (2024-05-16T06:07:31Z)
• Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
  一般化線形モデル (GLM) フレームワークを用いて, citelu2021low で提案した一般化低ランク行列帯域問題について検討する。 既存のアルゴリズムの計算不可能性と理論的制約を克服するため,まずG-ESTTフレームワークを提案する。 G-ESTT は $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret を達成でき、G-ESTS は $tildeO を達成できることを示す。
  論文  参考訳（メタデータ） (2024-01-14T14:14:19Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
  測定から学習した線形モデルの定量化の問題を考える。 この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。 本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
  論文  参考訳（メタデータ） (2022-02-23T02:39:04Z)
• Maillard Sampling: Boltzmann Exploration Done Optimally [11.282341369957216]
  この論文は、$K$武装バンディット問題に対するランダム化アルゴリズムを示す。 メイラードサンプリング(MS)は、各アームを閉じた形で選択する確率を計算する。 最適性を失わずに$sqrtKTlogK$に制限された最小値を改善するMS$+$というMSの変種を提案する。
  論文  参考訳（メタデータ） (2021-11-05T06:50:22Z)
• Randomized Exploration for Reinforcement Learning with General Value Function Approximation [122.70803181751135]
  本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。 提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。 我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
  論文  参考訳（メタデータ） (2021-06-15T02:23:07Z)
• Fully Gap-Dependent Bounds for Multinomial Logit Bandit [5.132017939561661]
  マルチノミアルロジット (MNL) バンディット問題について検討し、各ステップごとに、販売者は、N$アイテムのプールから最大でK$のサイズを提供する。 i) $widetildeO(sum_i = 1N Delta_i-2)$ time steps with high probability, (ii) $O(sum_i notin S* KDelta_i)というアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-11-19T17:52:12Z)
• Learning to Rank under Multinomial Logit Choice [6.929312022493406]
  コンテンツの最適順序付けを学ぶことは、ウェブサイト設計において重要な課題である。 本稿では,この問題に対する$Omega(sqrtJT)$lowbound,$tildeO(sqrtJT)$ upperbound on the regret of the UCBアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-09-07T16:15:12Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)
• Rate-adaptive model selection over a collection of black-box contextual bandit algorithms [0.966840768820136]
  文脈的帯域設定におけるモデル選択タスクについて検討する。 我々の提案は、一般的なブラックボックス・コンテクスト・バンディットアルゴリズムの収集に適応する最初のものである。
  論文  参考訳（メタデータ） (2020-06-05T18:55:16Z)
• Model Selection in Contextual Stochastic Bandit Problems [51.94632035240787]
  基本アルゴリズムを選択できるメタアルゴリズムを開発した。 基本アルゴリズムの1つが$O(sqrtT)$後悔している場合でも、一般的には$Omega(sqrtT)$後悔よりも良いものを得ることはできません。
  論文  参考訳（メタデータ） (2020-03-03T18:46:34Z)

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

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