論文の概要: MNL-Bandit with Knapsacks: a near-optimal algorithm
- arxiv url: http://arxiv.org/abs/2106.01135v3
- Date: Sat, 20 Jan 2024 17:23:05 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-24 00:36:54.611031
- Title: MNL-Bandit with Knapsacks: a near-optimal algorithm
- Title（参考訳）: Knapsacks を用いた MNL-Bandit 近似アルゴリズム
- Authors: Abdellah Aznag, Vineet Goyal and Noemie Perivier
- Abstract要約: 我々は,販売者が定額でN$の代替品を在庫する動的アソシエーション選択問題を考える。
各期間において、売り手は顧客に提供すべき商品の品揃えを決定する必要がある。
我々の政策は、大発明的な設定で、ほぼ最適に近い$tilde O(sqrtT)の後悔を達成します。
- 参考スコア（独自算出の注目度）: 2.3020018305241337
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider a dynamic assortment selection problem where a seller has a fixed
inventory of $N$ substitutable products and faces an unknown demand that
arrives sequentially over $T$ periods. In each period, the seller needs to
decide on the assortment of products (of cardinality at most $K$) to offer to
the customers. The customer's response follows an unknown multinomial logit
model (MNL) with parameters $v$. The goal of the seller is to maximize the
total expected revenue given the fixed initial inventory of $N$ products. We
give a policy that achieves a regret of $\tilde O\Big(K \sqrt{KN
T}\Big(\sqrt{v_{\text{max}}} + \frac{1}{q_{\text{min}}}\text{OPT}\Big)\Big)$,
where $v_{\text{max}}\leq 1$ is the maximum utility for any product and
$q_{\text{min}}$ the minimum inventory level, under a mild assumption on the
model parameters. In particular, our policy achieves a near-optimal $\tilde
O(\sqrt{T})$ regret in a large-inventory setting.
Our policy builds upon the UCB-based approach for MNL-bandit without
inventory constraints in [1] and addresses the inventory constraints through an
exponentially sized LP for which we present a tractable approximation while
keeping the $\tilde O(\sqrt{T})$ regret bound.
- Abstract（参考訳）: 販売者がN$の代替品の在庫を固定し、T$の期間に順次届く未知の需要に直面している場合の動的品揃え選択問題を考える。
各期間において、売り手は顧客に提供する製品(最大で1ドル)の品揃えを決定する必要がある。
顧客の応答は、パラメータ$v$を持つ未知の多項ロジットモデル(mnl)に従っている。
売り手の目標は、N$の商品の固定初期在庫から予想される総売上を最大化することである。
我々は、$\tilde o\big(k \sqrt{kn t}\big(\sqrt{v_{\text{max}}} + \frac{1}{q_{\text{min}}}\text{opt}\big)\big)$という後悔を達成するポリシーを与える。
特に、当社のポリシーは、大発明でほぼ最適に近い$\tilde o(\sqrt{t})$ regretを達成する。
当社のポリシーは,インベントリ制約のない mnl-bandit の [1] に対する ucb ベースのアプローチを基盤とし,$\tilde o(\sqrt{t})$ regret bound を維持しながら,扱いやすい近似を示す指数関数サイズの lp を通じて在庫制約に対処する。
関連論文リスト
- Improved Algorithms for Contextual Dynamic Pricing [24.530341596901476]
コンテキスト動的価格設定では、売り手はコンテキスト情報に基づいて商品を順次価格設定する。
提案アルゴリズムは,$tildemathcalO(T2/3)$の最適再帰限界を達成し,既存の結果を改善する。
このモデルに対して,我々のアルゴリズムは,文脈空間の次元を$d$とする,後悔の$tildemathcalO(Td+2beta/d+3beta)$を得る。
論文 参考訳（メタデータ） (2024-06-17T08:26:51Z) - Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。
我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。
技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
論文 参考訳（メタデータ） (2022-10-15T09:22:22Z) - No-Regret Learning in Partially-Informed Auctions [85.67897346422122]
本研究では,一部の情報を用いたオークションの機械学習定式化について検討する。
各ラウンドでは、未知の分布から新しいアイテムが引き出され、プラットフォームは、そのアイテムに関する不完全な「偽」情報とともに価格を発行する。
アイテムの分布が買い手に知られ、マスクがSimHash関数のマッピングである場合、$mathbbRd$ to $0,1ell$、我々のアルゴリズムは、$tilde MathcalO((Tdell)frac12)$を後悔している。
論文 参考訳（メタデータ） (2022-02-22T01:15:51Z) - Dynamic pricing and assortment under a contextual MNL demand [2.1320960069210475]
我々は、T期間における未知の需要の下で、動的多製品価格とアソシエーション問題を考察する。
オンラインニュートンステップアルゴリズム(ONS)の変種に基づくランダム化動的価格ポリシーを提案する。
また,MNLの文脈帯域幅問題に対する新しい楽観的アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-10-19T14:37:10Z) - Policy Optimization Using Semiparametric Models for Dynamic Pricing [1.3428344011390776]
商品の市場価値が観測された特徴と市場ノイズに線形である状況的動的価格問題について検討する。
一般化線形モデルからの半パラメトリック推定と未知のリンクとオンライン意思決定を組み合わせた動的統計的学習と意思決定ポリシーを提案する。
論文 参考訳（メタデータ） (2021-09-13T23:50:01Z) - Stochastic Shortest Path: Minimax, Parameter-Free and Towards
Horizon-Free Regret [144.6358229217845]
エージェントが目標状態に到達する前に蓄積される期待コストを最小限に抑えるために,最短経路(ssp)設定で学習する問題について検討する。
我々は,経験的遷移を慎重に歪曲し,探索ボーナスで経験的コストを摂動する新しいモデルベースアルゴリズムEB-SSPを設計する。
私達はEB-SSPが$widetildeO(B_star sqrtS A K)$のミニマックスの後悔率を達成することを証明します。
論文 参考訳（メタデータ） (2021-04-22T17:20:48Z) - UCB-based Algorithms for Multinomial Logistic Regression Bandits [31.67685495996986]
我々は、MNL(Multinomial logit)を用いて、K+1geq 2$の可能な結果の確率をモデル化する。
MNL-UCBは, 問題依存定数に小さな依存を伴い, $tildemathcalO(dKsqrtT)$を後悔する, 上位信頼境界(UCB)に基づくアルゴリズムである。
論文 参考訳（メタデータ） (2021-03-21T21:09:55Z) - Provably Efficient Reinforcement Learning with Linear Function
Approximation Under Adaptivity Constraints [94.76881135901753]
一般的な限定的適応モデルとして,バッチ学習モデルとレアポリシースイッチモデルがある。
提案したLSVI-UCB-Batchアルゴリズムは,$tilde O(sqrtd3H3T + dHT/B)$ regretを実現する。
まれなポリシスイッチモデルでは,提案されたLSVI-UCB-RareSwitchアルゴリズムは,$tilde O(sqrtd3H3T[1+T/(dH)]dH/B)$の後悔を享受する。
論文 参考訳（メタデータ） (2021-01-06T18:56: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) - Nearly Minimax Optimal Reinforcement Learning for Discounted MDPs [99.59319332864129]
UCBVI-$gamma$が$tildeObig(sqrtSAT/ (1-gamma)1.5big)$ regret, where $S$ is the number of state, $A$ is the number of action, $gamma$ is the discount factor, $T$ is the number of steps。
さらに、ハードMDPのクラスを構築し、任意のアルゴリズムに対して、期待される後悔は少なくとも$tildeOmegabig(sqrtSAT/)であることを示す。
論文 参考訳（メタデータ） (2020-10-01T17:57:47Z) - The Influence of Shape Constraints on the Thresholding Bandit Problem [74.73898216415049]
本稿では,いくつかの形状制約の下でThresholding Bandit問題(TBP)について検討する。
TBP問題において、目的は、シーケンシャルゲームの終わりに、所定のしきい値を超える手段を持つアームセットを出力することである。
後悔の最小値は (i) $sqrtlog(K)K/T$ for TBP, (ii) $sqrtlog(K)/T$ for UTBP, (iii) $sqrtK/T$ for CTBP, (iv) であることが証明されている。
論文 参考訳（メタデータ） (2020-06-17T17:12:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。