論文の概要: Improved Regret Bounds of (Multinomial) Logistic Bandits via
Regret-to-Confidence-Set Conversion
- arxiv url: http://arxiv.org/abs/2310.18554v3
- Date: Wed, 13 Mar 2024 02:58:07 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-14 11:16:59.033367
- Title: Improved Regret Bounds of (Multinomial) Logistic Bandits via
Regret-to-Confidence-Set Conversion
- Title（参考訳）: マルチノミカル)ロジスティックバンドのレグレト境界の改善
Regret-to-Confidence-Set変換
- Authors: Junghyun Lee, Se-Young Yun, Kwang-Sung Jun
- Abstract要約: 我々は,オンライン学習アルゴリズムのテキストテキシスタンスのみに基づく凸信頼セットを,後悔の保証付きで構築する。
R2CSを用いて、計算実現可能性を維持しながら、ロジスティックな包帯におけるw.r.t.$S$を厳格に改善する。
我々は,この分析を多項ロジスティック・バンディットにまで拡張し,R2CSの有効性を示した。
- 参考スコア（独自算出の注目度）: 40.159846982245746
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Logistic bandit is a ubiquitous framework of modeling users' choices, e.g.,
click vs. no click for advertisement recommender system. We observe that the
prior works overlook or neglect dependencies in $S \geq \lVert \theta_\star
\rVert_2$, where $\theta_\star \in \mathbb{R}^d$ is the unknown parameter
vector, which is particularly problematic when $S$ is large, e.g., $S \geq d$.
In this work, we improve the dependency on $S$ via a novel approach called {\it
regret-to-confidence set conversion (R2CS)}, which allows us to construct a
convex confidence set based on only the \textit{existence} of an online
learning algorithm with a regret guarantee. Using R2CS, we obtain a strict
improvement in the regret bound w.r.t. $S$ in logistic bandits while retaining
computational feasibility and the dependence on other factors such as $d$ and
$T$. We apply our new confidence set to the regret analyses of logistic bandits
with a new martingale concentration step that circumvents an additional factor
of $S$. We then extend this analysis to multinomial logistic bandits and obtain
similar improvements in the regret, showing the efficacy of R2CS. While we
applied R2CS to the (multinomial) logistic model, R2CS is a generic approach
for developing confidence sets that can be used for various models, which can
be of independent interest.
- Abstract（参考訳）: Logistic Banditは、ユーザの選択をモデル化するためのユビキタスフレームワークである。
ここで、$\theta_\star \in \mathbb{R}^d$は未知のパラメータベクトルであり、$S$が大きければ特に問題となる。
本研究は,オンライン学習アルゴリズムの「textit{existence}」のみに基づく凸信頼度セットを構築することができる「R2CS」と呼ばれる新しい手法により,$S$への依存性を改善するものである。
R2CSを用いると、ロジスティックな包帯においてw.r.t.$S$に対して、計算可能性を維持しながら、$d$や$T$などの他の要因に依存するような、厳格な改善が得られる。
我々は,ロジスティック・バンディットに対する新たな信頼度セットを,新たなマルティンゲール濃度ステップを用いて,S$の付加的要因を回避し,ロジスティック・バンディットの後悔分析に適用した。
次に,この分析を多項ロジスティック・バンディットに拡張し,同様の改善を加え,R2CSの有効性を示した。
我々は、R2CSを(多重項)ロジスティックモデルに適用したが、R2CSは、様々なモデルに使える信頼セットを開発するための一般的なアプローチであり、それは独立した関心を持つことができる。
関連論文リスト
- Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。
本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。
我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
論文 参考訳（メタデータ） (2023-10-02T08:15:52Z) - Bridging Distributional and Risk-sensitive Reinforcement Learning with
Provable Regret Bounds [24.571530193140916]
エントロピーリスク尺度(EntRM)が目的である有限エピソードマルコフ決定過程を考察する。
モデルフリーとモデルベースを含む2つの異なるスキームを用いて最適化を実装する2つの新しいDRLアルゴリズムを提案する。
いずれも$tildemathcalO(fracexp(|beta|H)-1|beta|HsqrtS2AK)$ regret upper bound, where $S$, $A$, $K$, $H$は数値を表す。
論文 参考訳（メタデータ） (2022-10-25T14:30:48Z) - Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms or Independent Arms [59.8188496313214]
半帯域 (CMAB) について検討し, 半帯域 (CMAB) におけるバッチサイズ (K$) の依存性の低減に着目した。
まず,確率的に引き起こされるアーム(CMAB-T)を用いたCMABの設定に対して,分散を考慮した信頼区間を持つBCUCB-Tアルゴリズムを提案する。
次に,独立アームを用いた非トリガ型CMABの設定に対して,TPVM条件の非トリガ型を利用したSESCBアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-08-31T13:09:39Z) - An Experimental Design Approach for Regret Minimization in Logistic
Bandits [26.674062544226636]
ロジスティックな盗賊の最大の課題は、潜在的に大きな問題に依存する定数$kappa$への依存を減らすことである。
そこで本研究では,新しいウォームアップサンプリングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-02-04T21:56:40Z) - Scale Free Adversarial Multi Armed Bandits [13.757095663704858]
本稿では,MAB(Scale-Free Adversarial Multi Armed Bandit)問題について考察する。
我々はFTRLアルゴリズムを設計するが、これはMABに対する最初の無スケールな後悔の保証が伴う。
また,Bregman Divergencesの局所ノルム下界を求める新しい手法を開発した。
論文 参考訳（メタデータ） (2021-06-08T21:26:57Z) - Improved Analysis of Robustness of the Tsallis-INF Algorithm to
Adversarial Corruptions in Stochastic Multiarmed Bandits [12.462608802359936]
Zimmert and Seldin (2021) の Tsallis-INF アルゴリズムに対する後悔の境界を改善した。
特に、$C = Thetaleft(fracTlog Tlog T$)$の場合、$T$が時空である場合、乗算因子による改善を達成します。
また, time horizon 上の後悔の依存性を $log t$ から $log frac(k-1)t(sum_ineq i*frac1delta_ に改善する。
論文 参考訳（メタデータ） (2021-03-23T12:26:39Z) - Variance-Aware Confidence Set: Variance-Dependent Bound for Linear
Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
線形バンドイットと線形混合決定プロセス(mdp)に対する分散認識信頼セットの構築方法を示す。
線形バンドイットに対しては、$d を特徴次元とする$widetildeo(mathrmpoly(d)sqrt1 + sum_i=1ksigma_i2) が成り立つ。
線形混合 MDP に対し、$widetildeO(mathrmpoly(d)sqrtK)$ regret bound を得る。
論文 参考訳（メタデータ） (2021-01-29T18:57:52Z) - 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) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z) - Improved Optimistic Algorithms for Logistic Bandits [16.140301473601454]
そこで本稿では,報酬関数の非線形性について,より詳細な検証に基づく新しい楽観的アルゴリズムを提案する。
我々は、$tildemathcalO(sqrtT)$ regretを楽しんでおり、$kappa$に依存しないが、第2の順序の項には依存しないことを示す。
論文 参考訳（メタデータ） (2020-02-18T12:52:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。