論文の概要: A Tractable Online Learning Algorithm for the Multinomial Logit Contextual Bandit
- arxiv url: http://arxiv.org/abs/2011.14033v7
- Date: Sun, 14 Apr 2024 14:47:24 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-17 00:52:57.686094
- Title: A Tractable Online Learning Algorithm for the Multinomial Logit Contextual Bandit
- Title（参考訳）: 多項ロジト文脈帯域のトラクタブルオンライン学習アルゴリズム
- Authors: Priyank Agrawal, Theja Tulabandhula, Vashist Avadhanula,
- Abstract要約: 我々は、意思決定者が消費者に製品のサブセットを提供する動的集合最適化問題を考える。
MNL(Multinomial Logit)モデルを用いて消費者選択行動のモデル化を行う。
後悔は$O(sqrtdT + kappa)$で束縛され、既存のメソッドよりもパフォーマンスが大幅に向上していることを示す。
- 参考スコア（独自算出の注目度）: 2.9998316151418107
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we consider the contextual variant of the MNL-Bandit problem. More specifically, we consider a dynamic set optimization problem, where a decision-maker offers a subset (assortment) of products to a consumer and observes the response in every round. Consumers purchase products to maximize their utility. We assume that a set of attributes describe the products, and the mean utility of a product is linear in the values of these attributes. We model consumer choice behavior using the widely used Multinomial Logit (MNL) model and consider the decision maker problem of dynamically learning the model parameters while optimizing cumulative revenue over the selling horizon $T$. Though this problem has attracted considerable attention in recent times, many existing methods often involve solving an intractable non-convex optimization problem. Their theoretical performance guarantees depend on a problem-dependent parameter which could be prohibitively large. In particular, existing algorithms for this problem have regret bounded by $O(\sqrt{\kappa d T})$, where $\kappa$ is a problem-dependent constant that can have an exponential dependency on the number of attributes. In this paper, we propose an optimistic algorithm and show that the regret is bounded by $O(\sqrt{dT} + \kappa)$, significantly improving the performance over existing methods. Further, we propose a convex relaxation of the optimization step, which allows for tractable decision-making while retaining the favourable regret guarantee.
- Abstract（参考訳）: 本稿では,MNL-Bandit問題の文脈変化について考察する。
より具体的には、動的集合最適化の問題を考察し、意思決定者は消費者に製品のサブセット(構成)を提供し、各ラウンドで反応を観察する。
消費者は有用性を最大化するために製品を購入します。
属性の集合が製品を記述すると仮定し、製品の平均効用はこれらの属性の値において線形であると仮定する。
我々は,広く使用されているMNLモデルを用いて消費者選択行動のモデル化を行い,モデルパラメータを動的に学習する決定者問題について考察する。
この問題は近年注目されているが、既存の多くの手法では難解な非凸最適化問題を解くことがしばしばある。
理論的な性能保証は問題に依存したパラメータに依存しており、これは違法に大きい可能性がある。
特に、この問題に対する既存のアルゴリズムは、$O(\sqrt{\kappa d T})$で制限されている。
本稿では,楽観的なアルゴリズムを提案し,その後悔は$O(\sqrt{dT} + \kappa)$で束縛されていることを示す。
さらに, 提案手法は, 好意的な後悔の保証を保ちながら, トラクタブルな意思決定を可能にする, 最適化ステップの凸緩和を提案する。
関連論文リスト
- Minimax Optimality in Contextual Dynamic Pricing with General Valuation Models [4.156757591117864]
本稿では,問題に対する仮定を最小化しながら,改善された後悔境界を実現する新しいアルゴリズムを提案する。
本手法は, 一般関数空間を考慮し, 動的価格設定によく用いられる線形評価モデルを超えて拡張する。
論文 参考訳（メタデータ） (2024-06-24T23:43:56Z) - Stop Relying on No-Choice and Do not Repeat the Moves: Optimal,
Efficient and Practical Algorithms for Assortment Optimization [38.57171985309975]
本研究では,emphPlackett Luce (PL) を用いたコンソーシアム選択問題に対する効率的なアルゴリズムを開発した。
提案手法は,既存の手法の限界を無視し,実用的かつ確実に最適である。
論文 参考訳（メタデータ） (2024-02-29T07:17:04Z) - End-to-End Learning for Fair Multiobjective Optimization Under
Uncertainty [55.04219793298687]
機械学習における予測-Then-Forecast(PtO)パラダイムは、下流の意思決定品質を最大化することを目的としている。
本稿では,PtO法を拡張して,OWA(Nondifferentiable Ordered Weighted Averaging)の目的を最適化する。
この結果から,不確実性の下でのOWA関数の最適化とパラメトリック予測を効果的に統合できることが示唆された。
論文 参考訳（メタデータ） (2024-02-12T16:33:35Z) - Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement
Learning: Adaptivity and Computational Efficiency [90.40062452292091]
本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。
我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。
また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-02-21T00:17:24Z) - Symmetric Tensor Networks for Generative Modeling and Constrained
Combinatorial Optimization [72.41480594026815]
ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。
これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。
本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
論文 参考訳（メタデータ） (2022-11-16T18:59:54Z) - Markov Decision Process modeled with Bandits for Sequential Decision
Making in Linear-flow [73.1896399783641]
会員/加入者の獲得と保持では、複数のページを連続してマーケティングコンテンツを推奨する必要がある。
遷移確率行列をモデル化するためにBandits を用いた MDP としてこの問題を定式化することを提案する。
提案したMDPのBanditsアルゴリズムは,$epsilon$-greedyと$epsilon$-greedy,$epsilon$,IndependentBandits,InteractionBanditsでQ-learningを上回っている。
論文 参考訳（メタデータ） (2021-07-01T03:54:36Z) - Online Model Selection for Reinforcement Learning with Function
Approximation [50.008542459050155]
我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。
また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
論文 参考訳（メタデータ） (2020-11-19T10:00:54Z) - Alternating Direction Method of Multipliers for Quantization [15.62692130672419]
量子化のための乗算器の交互方向法(texttADMM-Q$)アルゴリズムの性能について検討する。
不正確な更新ルールを処理できる$texttADMM-Q$のいくつかのバリエーションを開発しています。
提案手法の有効性を実証的に評価した。
論文 参考訳（メタデータ） (2020-09-08T01:58:02Z) - Efficient Optimistic Exploration in Linear-Quadratic Regulators via
Lagrangian Relaxation [107.06364966905821]
線形2次レギュレータ(LQR)設定における探索・探索ジレンマについて検討した。
有限 MDP に対する楽観的アルゴリズムで用いられる拡張値反復アルゴリズムに着想を得て,Oulq の楽観的最適化を緩和することを提案する。
我々は、少なくとも$Obig(log (1/epsilon)big)$ Riccati方程式を解くことで、$epsilon$-OptimisticControllerを効率的に計算できることを示した。
論文 参考訳（メタデータ） (2020-07-13T16:30:47Z) - Constrained Multiagent Rollout and Multidimensional Assignment with the
Auction Algorithm [0.0]
本稿では,制約付き決定論的動的プログラミングに適用可能なロールアウトアルゴリズムの拡張について考察する。
提案手法では,ベースが実現可能な解を生成する場合,ロールアウトアルゴリズムはコスト改善特性を有することを示す。
コスト改善特性は計算要求を大幅に削減した代替実装で維持されていることを示す。
論文 参考訳（メタデータ） (2020-02-18T07:09:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。