論文の概要: Multinomial Logit Bandit with Low Switching Cost
- arxiv url: http://arxiv.org/abs/2007.04876v1
- Date: Thu, 9 Jul 2020 15:26:54 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-12 03:30:46.599520
- Title: Multinomial Logit Bandit with Low Switching Cost
- Title（参考訳）: 低スイッチングコストのマルチノードロジットバンド
- Authors: Kefan Dong, Yingkai Li, Qin Zhang, Yuan Zhou
- Abstract要約: 適応性に制限のある多項ロジットバンディットについて検討した。
本稿では, 品目切り換えコストと, よりきめ細かい品目切り換えコストの2つの適応性尺度を提案する。
- 参考スコア（独自算出の注目度）: 18.44502766099436
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study multinomial logit bandit with limited adaptivity, where the
algorithms change their exploration actions as infrequently as possible when
achieving almost optimal minimax regret. We propose two measures of adaptivity:
the assortment switching cost and the more fine-grained item switching cost. We
present an anytime algorithm (AT-DUCB) with $O(N \log T)$ assortment switches,
almost matching the lower bound $\Omega(\frac{N \log T}{ \log \log T})$. In the
fixed-horizon setting, our algorithm FH-DUCB incurs $O(N \log \log T)$
assortment switches, matching the asymptotic lower bound. We also present the
ESUCB algorithm with item switching cost $O(N \log^2 T)$.
- Abstract（参考訳）: 適応性が限定されたマルチノミナルロジットバンディットについて検討し, アルゴリズムは, ほとんど最適のミニマックス後悔を達成する際に, 探索動作をできるだけ頻繁に変更する。
適応性の尺度として, 仕分け切替コストと細粒度切換コストの2つを提案する。
我々は、$O(N \log T)$ Assortment switchsで、下限の$\Omega(\frac{N \log T}{ \log \log T})$とほぼ一致する任意のアルゴリズム(AT-DUCB)を示す。
固定水平設定では、FH-DUCBアルゴリズムは、漸近的下界に一致する$O(N \log \log T)$アソートスイッチを発生させる。
また,アイテム切替コストを$O(N \log^2T)$とするESACBアルゴリズムを提案する。
関連論文リスト
- Batched Stochastic Bandit for Nondegenerate Functions [8.015503209312786]
本稿では,非退化関数に対するバッチ帯域学習問題について検討する。
本稿では,非退化関数に対するバッチバンドイット問題をほぼ最適に解くアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-05-09T12:50:16Z) - Near-Optimal Reinforcement Learning with Self-Play under Adaptivity
Constraints [21.412085244757336]
適応性制約を伴うマルチエージェント強化学習(MARL)の問題について検討する。
2つのプレイヤーゼロサムマルコフゲームに対して、$widetildeO(sqrtH3 S2 ABK)$を後悔する(政治)排除に基づくアルゴリズムを設計する。
バッチ複雑性の低い$Omega(fracHlog_AK+loglog K)$を$widetildeO(sqrtK)$で証明する。
論文 参考訳（メタデータ） (2024-02-02T03:00:40Z) - 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) - Sample-Efficient Reinforcement Learning with loglog(T) Switching Cost [31.04961854943877]
我々は,$widetildeO(sqrtH4S2AT)$を,切り替えコストが$O(HSA loglog T)$を要求されたことを後悔する新しいアルゴリズムを提案する。
副産物として、我々の新しいアルゴリズムは、最適な切替コストが$O(HSA)$のエンフレワードフリー探索アルゴリズムを導出することができる。
論文 参考訳（メタデータ） (2022-02-13T19:01:06Z) - Corralling a Larger Band of Bandits: A Case Study on Switching Regret
for Linear Bandits [99.86860277006318]
本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。
Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。
この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
論文 参考訳（メタデータ） (2022-02-12T21:55:44Z) - Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
有限腕バンディットアルゴリズムにインスパイアされたバッチアルゴリズムを導入する。
O(log T)$ batches in time horizon $T$.sqrtTgamma_T)$ using $O(log T)$ batches in time horizon。
さらに,アルゴリズムの修正版を提案し,バッチ数によって後悔がどう影響するかを特徴付ける。
論文 参考訳（メタデータ） (2021-10-15T00:54:04Z) - Online Convex Optimization with Continuous Switching Constraint [78.25064451417082]
連続的なスイッチング制約を伴うオンライン凸最適化の問題を紹介する。
強い凸関数の場合、後悔境界は$O(log T)$ for $S=Omega(log T)$、$O(minT/exp(S)+S,T)$ for $S=O(log T)$に改善できることを示す。
論文 参考訳（メタデータ） (2021-03-21T11:43:35Z) - A Provably Efficient Algorithm for Linear Markov Decision Process with
Low Switching Cost [53.968049198926444]
スイッチングコストの低い線形MDPのための最初のアルゴリズムを提案する。
このアルゴリズムは$widetildeoleft(sqrtd3h4kright)$ regretをほぼ最適の$oleft(d hlog kright)$グローバルスイッチングコストで達成する。
論文 参考訳（メタデータ） (2021-01-02T18:41:27Z) - 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) - Thresholded Lasso Bandit [70.17389393497125]
Thresholded Lasso banditは、報酬関数を定義するベクトルとスパースサポートを推定するアルゴリズムである。
一般には $mathcalO( log d + sqrtT )$ や $mathcalO( log d + sqrtT )$ としてスケールする非漸近的後悔の上界を確立する。
論文 参考訳（メタデータ） (2020-10-22T19:14:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。