論文の概要: MNL-Bandit with Knapsacks: a near-optimal algorithm
- arxiv url: http://arxiv.org/abs/2106.01135v5
- Date: Wed, 24 Jan 2024 14:56:44 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-25 11:56:42.766648
- Title: MNL-Bandit with Knapsacks: a near-optimal algorithm
- Title（参考訳）: Knapsacks を用いた MNL-Bandit 近似アルゴリズム
- Authors: Abdellah Aznag, Vineet Goyal and Noemie Perivier
- Abstract要約: 我々は,販売者が定額でN$の代替品を在庫する動的アソシエーション選択問題を考える。
各期間において、売り手は顧客に提供すべき商品の品揃えを決定する必要がある。
MNLwK-UCB は,在庫規模がほぼ直線的に大きくなると,$tildeO(N + sqrtNT)$ regret bound が得られることを示す。
- 参考スコア（独自算出の注目度）: 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 (satisfying certain constraints) to offer
to the customers. The customer's response follows an unknown multinomial logit
model (MNL) with parameter $\boldsymbol{v}$. If customer selects product $i \in
[N]$, the seller receives revenue $r_i$. The goal of the seller is to maximize
the total expected revenue from the $T$ customers given the fixed initial
inventory of $N$ products. We present MNLwK-UCB, a UCB-based algorithm and
characterize its regret under different regimes of inventory size. We show that
when the inventory size grows quasi-linearly in time, MNLwK-UCB achieves a
$\tilde{O}(N + \sqrt{NT})$ regret bound. We also show that for a smaller
inventory (with growth $\sim T^{\alpha}$, $\alpha < 1$), MNLwK-UCB achieves a
$\tilde{O}(N(1 + T^{\frac{1 - \alpha}{2}}) + \sqrt{NT})$. In particular, over a
long time horizon $T$, the rate $\tilde{O}(\sqrt{NT})$ is always achieved
regardless of the constraints and the size of the inventory.
- Abstract（参考訳）: 販売者がN$の代替品の在庫を固定し、T$の期間に順次届く未知の需要に直面している場合の動的品揃え選択問題を考える。
各期間において、売り手は顧客に提供する製品の品揃え(一定の制約を満たす)を決定する必要がある。
顧客の応答は、パラメータ$\boldsymbol{v}$を持つ未知の多項ロジットモデル(mnl)に従っている。
顧客が商品$i \in [N]$を選択すると、売り手は収入$r_i$を受け取る。
販売者の目標は、n$製品の初期在庫が固定された場合、t$顧客から期待される総売上を最大化することである。
UCBに基づくアルゴリズムであるMNLwK-UCBを提案する。
MNLwK-UCB は、在庫規模が時間的に準直線的に大きくなると、$\tilde{O}(N + \sqrt{NT})$ regret bound が得られる。
また、より小さな在庫(成長$\sim T^{\alpha}$, $\alpha < 1$)の場合、MNLwK-UCB は $\tilde{O}(N(1 + T^{\frac{1 - \alpha}{2}}) + \sqrt{NT})$ を達成する。
特に、長い時間的地平線において、$\tilde{O}(\sqrt{NT})$ は在庫の制約や大きさに関わらず常に達成される。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。