論文の概要: Fully Gap-Dependent Bounds for Multinomial Logit Bandit

• arxiv url: http://arxiv.org/abs/2011.09998v1
• Date: Thu, 19 Nov 2020 17:52:12 GMT
• ステータス: 処理完了
• システム内更新日: 2022-09-23 21:25:52.215891
• Title: Fully Gap-Dependent Bounds for Multinomial Logit Bandit
• Title（参考訳）: 多項ロジットバンドに対する完全ギャップ依存境界
• Authors: Jiaqi Yang
• Abstract要約: マルチノミアルロジット (MNL) バンディット問題について検討し、各ステップごとに、販売者は、N$アイテムのプールから最大でK$のサイズを提供する。 i) $widetildeO(sum_i = 1N Delta_i-2)$ time steps with high probability, (ii) $O(sum_i notin S* KDelta_i)というアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 5.132017939561661
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the multinomial logit (MNL) bandit problem, where at each time step, the seller offers an assortment of size at most $K$ from a pool of $N$ items, and the buyer purchases an item from the assortment according to a MNL choice model. The objective is to learn the model parameters and maximize the expected revenue. We present (i) an algorithm that identifies the optimal assortment $S^*$ within $\widetilde{O}(\sum_{i = 1}^N \Delta_i^{-2})$ time steps with high probability, and (ii) an algorithm that incurs $O(\sum_{i \notin S^*} K\Delta_i^{-1} \log T)$ regret in $T$ time steps. To our knowledge, our algorithms are the first to achieve gap-dependent bounds that fully depends on the suboptimality gaps of all items. Our technical contributions include an algorithmic framework that relates the MNL-bandit problem to a variant of the top-$K$ arm identification problem in multi-armed bandits, a generalized epoch-based offering procedure, and a layer-based adaptive estimation procedure.
• Abstract（参考訳）: 我々は,マルチノミナルロジット (mnl) のバンディット問題について検討し,各時間ステップにおいて,販売者は,n$ アイテムのプールから最大$k$ の品揃えを提供し,購入者は mnl 選択モデルに従ってその品目からアイテムを購入する。 目標はモデルパラメータを学習し、期待される収益を最大化することです。 ご紹介します (i)$S^*$を$\widetilde{O}(\sum_{i = 1}^N \Delta_i^{-2})$高確率の時間ステップで識別するアルゴリズム。 (ii)$o(\sum_{i \notin s^*} k\delta_i^{-1} \log t)$の時間ステップで後悔するアルゴリズム。 我々の知る限り、我々のアルゴリズムは、すべての項目の最適以下のギャップに完全に依存するギャップ依存境界を達成した最初のアルゴリズムである。 我々の技術貢献には、MNLバンド問題とマルチアームバンディットにおけるトップ$K$アーム識別問題の変種を関連付けるアルゴリズムフレームワーク、一般化エポックベースの提供手順、層ベースの適応推定手順が含まれる。

関連論文リスト

• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
  相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。 注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。 本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
  論文  参考訳（メタデータ） (2023-06-30T08:34:29Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Multinomial Logit Contextual Bandits: Provable Optimality and Practicality [15.533842336139063]
  パラメータが不明な多項式ロギット(MNL)選択モデルによってユーザ選択が与えられる順序選択選択問題を検討する。 本稿では,このMNLコンテクストバンディットに対する高信頼境界に基づくアルゴリズムを提案する。 本稿では,アルゴリズムの単純な変種が,幅広い重要なアプリケーションに対して最適な後悔を与えることを示す。
  論文  参考訳（メタデータ） (2021-03-25T15:42:25Z)
• Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy [71.17938026619068]
  我々は、腕の総数が膨大であることができるトップ$ k$極端な文脈的包帯問題を研究します。 まず,Inverse Gap Weighting戦略を用いて,非極端に実現可能な設定のアルゴリズムを提案する。 我々のアルゴリズムは、$O(ksqrt(A-k+1)T log (|mathcalF|T))$である。
  論文  参考訳（メタデータ） (2021-02-15T19:10:52Z)
• A Multi-Arm Bandit Approach To Subset Selection Under Constraints [14.543433698096667]
  中央プランナーがエージェントのサブセットを選択する必要がある問題の種類を,それぞれ異なる品質とコストで検討する。 エージェントの品質が分かると、我々は問題を整数線形プログラム(ILP)として定式化する。 ILPの正確な解を提供する決定論的アルゴリズム(dpss)を提案する。
  論文  参考訳（メタデータ） (2021-02-09T13:48:57Z)
• Practical and Parallelizable Algorithms for Non-Monotone Submodular Maximization with Size Constraint [20.104148319012854]
  サイズ制約に関して、必ずしも単調ではない部分モジュラ函数に対して存在および並列化可能である。 最適な適応性とほぼ最適な複雑性クエリを持つアルゴリズムによって達成される最適な近似係数を、0.193 - varepsilon$に改善する。
  論文  参考訳（メタデータ） (2020-09-03T22:43:55Z)
• Revisiting Modified Greedy Algorithm for Monotone Submodular Maximization with a Knapsack Constraint [75.85952446237599]
  修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。 最適なデータ依存上界を導出する。 また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
  論文  参考訳（メタデータ） (2020-08-12T15:40:21Z)
• Optimal $\delta$-Correct Best-Arm Selection for Heavy-Tailed Distributions [2.2940141855172036]
  我々は、$delta$-correctアルゴリズムを用いて、最大平均値を持つものを識別する問題を考察する。 $delta$-correctアルゴリズムの下位境界はよく知られている。 我々は,下界の$delta$-correctアルゴリズムを提案し,$delta$を0に還元する。
  論文  参考訳（メタデータ） (2019-08-24T05:31:49Z)

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

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