論文の概要: Nearly Minimax Optimal Regret for Multinomial Logistic Bandit
- arxiv url: http://arxiv.org/abs/2405.09831v6
- Date: Sun, 03 Nov 2024 00:58:36 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-05 14:44:25.950361
- Title: Nearly Minimax Optimal Regret for Multinomial Logistic Bandit
- Title（参考訳）: 多項ロジスティック帯域に対する極小最小レグレット
- Authors: Joongkyu Lee, Min-hwan Oh,
- Abstract要約: 本研究では,学習エージェントが文脈情報に基づいて順にアソシエーションを選択する,文脈多項ロジット(MNL)バンディット問題について検討する。
特に最大品位が$K$の場合には、下限と上限の差が顕著である。
定数時間アルゴリズム OFU-MNL+ を提案し, 一致する上限を $tildeO(dsqrtsmash[b]T/K)$ とする。
- 参考スコア（独自算出の注目度）: 8.087699764574788
- License:
- Abstract: In this paper, we study the contextual multinomial logit (MNL) bandit problem in which a learning agent sequentially selects an assortment based on contextual information, and user feedback follows an MNL choice model. There has been a significant discrepancy between lower and upper regret bounds, particularly regarding the maximum assortment size $K$. Additionally, the variation in reward structures between these bounds complicates the quest for optimality. Under uniform rewards, where all items have the same expected reward, we establish a regret lower bound of $\Omega(d\sqrt{\smash[b]{T/K}})$ and propose a constant-time algorithm, OFU-MNL+, that achieves a matching upper bound of $\tilde{O}(d\sqrt{\smash[b]{T/K}})$. We also provide instance-dependent minimax regret bounds under uniform rewards. Under non-uniform rewards, we prove a lower bound of $\Omega(d\sqrt{T})$ and an upper bound of $\tilde{O}(d\sqrt{T})$, also achievable by OFU-MNL+. Our empirical studies support these theoretical findings. To the best of our knowledge, this is the first work in the contextual MNL bandit literature to prove minimax optimality -- for either uniform or non-uniform reward setting -- and to propose a computationally efficient algorithm that achieves this optimality up to logarithmic factors.
- Abstract（参考訳）: 本稿では,学習エージェントがコンテキスト情報に基づいて順にアソシエーションを選択し,ユーザからのフィードバックがMNL選択モデルに従うという,コンテキスト多項ロジット(MNL)バンディット問題について検討する。
特に最大品位が$K$の場合には、下限と上限の差が顕著である。
さらに、これらの境界の間の報酬構造の変化は、最適性の探求を複雑にする。
すべてのアイテムが同じ期待される報酬を持つ一様報酬の下で、後悔の少ない$\Omega(d\sqrt{\smash[b]{T/K}})$を確立し、一致する上限の$\tilde{O}(d\sqrt{\smash[b]{T/K}})$を達成する定数時間アルゴリズム OFU-MNL+を提案する。
また、一様報酬の下で、インスタンス依存のミニマックス後悔境界も提供する。
非一様報酬の下では、$\Omega(d\sqrt{T})$の下位境界と$\tilde{O}(d\sqrt{T})$の上限を証明し、OFU-MNL+によっても達成できる。
我々の実証研究はこれらの理論的な発見を支持している。
我々の知る限りでは、これは文脈的 MNL バンディット文学において、一様あるいは一様でない報酬設定に対して最小の最適性を証明し、この最適性を対数的要因まで達成する計算効率の良いアルゴリズムを提案する最初の作品である。
関連論文リスト
- Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Communication-Constrained Bandits under Additive Gaussian Noise [111.06688156723018]
クライアントが学習者にコミュニケーション制約のあるフィードバックを提供する分散マルチアームバンディットについて検討する。
我々は、この下限を小さな加法係数にマッチさせるマルチフェーズ帯域幅アルゴリズム、$mathtUEtext-UCB++$を提案する。
論文 参考訳（メタデータ） (2023-04-25T09:31:20Z) - Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaR [58.40575099910538]
本研究は,リスク許容度が$tau$のCVaR(Conditional Value at Risk)の目的に着目し,リスクに敏感な強化学習(RL)について検討する。
ミニマックスCVaRの後悔率は$Omega(sqrttau-1AK)$で、$A$はアクションの数、$K$はエピソード数である。
我々は,このアルゴリズムが連続性仮定の下で$widetilde O(tau-1sqrtSAK)$の最適後悔を達成し,一般に近似することを示す。
論文 参考訳（メタデータ） (2023-02-07T02:22:31Z) - Maillard Sampling: Boltzmann Exploration Done Optimally [11.282341369957216]
この論文は、$K$武装バンディット問題に対するランダム化アルゴリズムを示す。
メイラードサンプリング(MS)は、各アームを閉じた形で選択する確率を計算する。
最適性を失わずに$sqrtKTlogK$に制限された最小値を改善するMS$+$というMSの変種を提案する。
論文 参考訳（メタデータ） (2021-11-05T06:50:22Z) - Multinomial Logit Contextual Bandits: Provable Optimality and
Practicality [15.533842336139063]
パラメータが不明な多項式ロギット(MNL)選択モデルによってユーザ選択が与えられる順序選択選択問題を検討する。
本稿では,このMNLコンテクストバンディットに対する高信頼境界に基づくアルゴリズムを提案する。
本稿では,アルゴリズムの単純な変種が,幅広い重要なアプリケーションに対して最適な後悔を与えることを示す。
論文 参考訳（メタデータ） (2021-03-25T15:42:25Z) - Provably Breaking the Quadratic Error Compounding Barrier in Imitation
Learning, Optimally [58.463668865380946]
状態空間 $mathcalS$ を用いたエピソードマルコフ決定過程 (MDPs) における模擬学習の統計的限界について検討する。
rajaraman et al (2020) におけるmdアルゴリズムを用いた準最適性に対する上限 $o(|mathcals|h3/2/n)$ を定式化する。
Omega(H3/2/N)$ $mathcalS|geq 3$ であるのに対して、未知の遷移条件はよりシャープレートに悩まされる。
論文 参考訳（メタデータ） (2021-02-25T15:50:19Z) - Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits
with Linear Payoff Functions [53.77572276969548]
我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。
一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-20T04:29:18Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。