論文の概要: Linear Contextual Bandits with Hybrid Payoff: Revisited
- arxiv url: http://arxiv.org/abs/2406.10131v2
- Date: Tue, 3 Sep 2024 20:13:24 GMT
- ステータス: 処理完了
- システム内更新日: 2024-09-07 02:31:44.655546
- Title: Linear Contextual Bandits with Hybrid Payoff: Revisited
- Title（参考訳）: ハイブリッドペイオフ付き線形コンテキスト帯域:再考
- Authors: Nirjhar Das, Gaurav Sinha,
- Abstract要約: ハイブリッド報酬設定における線形文脈問題について検討する。
この設定では、各アームの報酬モデルには、すべてのアームの報酬モデル間で共有されるパラメータに加えて、アーム固有のパラメータが含まれる。
- 参考スコア（独自算出の注目度）: 0.8287206589886881
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: We study the Linear Contextual Bandit problem in the hybrid reward setting. In this setting every arm's reward model contains arm specific parameters in addition to parameters shared across the reward models of all the arms. We can reduce this setting to two closely related settings (a) Shared - no arm specific parameters, and (b) Disjoint - only arm specific parameters, enabling the application of two popular state of the art algorithms - $\texttt{LinUCB}$ and $\texttt{DisLinUCB}$ (Algorithm 1 in (Li et al. 2010)). When the arm features are stochastic and satisfy a popular diversity condition, we provide new regret analyses for both algorithms, significantly improving on the known regret guarantees of these algorithms. Our novel analysis critically exploits the hybrid reward structure and the diversity condition. Moreover, we introduce a new algorithm $\texttt{HyLinUCB}$ that crucially modifies $\texttt{LinUCB}$ (using a new exploration coefficient) to account for sparsity in the hybrid setting. Under the same diversity assumptions, we prove that $\texttt{HyLinUCB}$ also incurs only $O(\sqrt{T})$ regret for $T$ rounds. We perform extensive experiments on synthetic and real-world datasets demonstrating strong empirical performance of $\texttt{HyLinUCB}$.For number of arm specific parameters much larger than the number of shared parameters, we observe that $\texttt{DisLinUCB}$ incurs the lowest regret. In this case, regret of $\texttt{HyLinUCB}$ is the second best and extremely competitive to $\texttt{DisLinUCB}$. In all other situations, including our real-world dataset, $\texttt{HyLinUCB}$ has significantly lower regret than $\texttt{LinUCB}$, $\texttt{DisLinUCB}$ and other SOTA baselines we considered. We also empirically observe that the regret of $\texttt{HyLinUCB}$ grows much slower with the number of arms compared to baselines, making it suitable even for very large action spaces.
- Abstract（参考訳）: ハイブリッド報酬設定における線形文脈帯域問題について検討する。
この設定では、各アームの報酬モデルには、すべてのアームの報酬モデル間で共有されるパラメータに加えて、アーム固有のパラメータが含まれる。
この設定を2つの密接に関連する設定に減らすことができます
(a)共有 - 腕固有のパラメータがなく、
b) Disjoint - アーム固有のパラメータのみを使用し、2つの一般的な最先端アルゴリズム($\texttt{LinUCB}$と$\texttt{DisLinUCB}$(Algorithm 1 in (Li et al 2010))を適用可能にする。
腕の特徴が確率的であり、一般的な多様性条件を満たす場合、両アルゴリズムに新たな後悔分析を提供し、これらのアルゴリズムの既知の後悔の保証を著しく改善する。
本稿では,ハイブリッド報酬構造と多様性条件を批判的に活用する。
さらに, ハイブリッド環境における疎度を考慮に入れた新たなアルゴリズムである $\texttt{HyLinUCB}$ を導入する。
同じ多様性の仮定の下では、$\texttt{HyLinUCB}$もまた$O(\sqrt{T})$ regret for $T$ roundsを発生させる。
我々は,合成および実世界のデータセットに対して,$\texttt{HyLinUCB}$の強い経験的性能を示す広範な実験を行った。
共有パラメータの数よりもはるかに大きいアーム特定パラメータの数に対して、$\texttt{DisLinUCB}$が最小の後悔を引き起こす。
この場合、$\texttt{HyLinUCB}$に対する後悔は、$\texttt{DisLinUCB}$に対する2番目の最良の競合である。
実世界のデータセットを含む他の状況では、$\texttt{HyLinUCB}$は、$\textt{LinUCB}$、$\texttt{DisLinUCB}$、その他のSOTAベースラインよりも大幅に低い。
また、例えば$\texttt{HyLinUCB}$の後悔は、ベースラインよりも腕の数が多いほど遅くなり、非常に大きなアクション空間にも適していることを実証的に観察する。
関連論文リスト
- Federated UCBVI: Communication-Efficient Federated Regret Minimization with Heterogeneous Agents [13.391318494060975]
We present the Federated upper Confidence bound Value Iteration algorithm (textttFed-UCBVI$)
textttFed-UCBVI$ の後悔は $tildemathcalO(sqrtH3 |mathcalS| |mathcalA| T / M)$ としてスケールすることを証明する。
既存の強化学習アプローチとは異なり、$textttFed-UCBVI$の通信複雑性は、その数によってわずかに増加する。
論文 参考訳（メタデータ） (2024-10-30T11:05:50Z) - Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳（メタデータ） (2023-12-13T11:08:25Z) - Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
確率的に誘発される腕(C$2$MAB-T)を様々な滑らかさ条件下で検討した。
トリガー変調 (TPM) 条件の下では、C$2$-UC-Tアルゴリズムを考案し、後悔すべき$tildeO(dsqrtT)$を導出する。
論文 参考訳（メタデータ） (2023-03-30T02:51:00Z) - Revisiting Simple Regret Minimization in Multi-Armed Bandits [33.88679679593314]
単純な後悔は、最高の腕や$epsilon$-good腕を欠く確率よりもあまり一般的ではない。
本稿では,データ豊かさ (Tge n$) とデータ貧弱さ (T le n$) の両面において,単純な後悔の上限を改良した。
より困難なデータ・ポーア・レシエーションのために、少なくとも1回は各腕をサンプリングすることなく、同じ改善を享受できるブラッケティングSH(BSH)を提案する。
論文 参考訳（メタデータ） (2022-10-30T18:31:03Z) - Double Doubly Robust Thompson Sampling for Generalized Linear Contextual
Bandits [8.508198765617198]
一般化線形報酬に$tildeO(sqrtkappa-1 phi T)$ regret over $T$ roundsを提案する。
また、確率的マージン条件下では、$O(kappa-1 phi log (NT) log T)$ regret bound for $N$ arms も提供する。
論文 参考訳（メタデータ） (2022-09-15T00:20:38Z) - Regret Lower Bound and Optimal Algorithm for High-Dimensional Contextual
Linear Bandit [10.604939762790517]
我々は、累積後悔に対して、$mathcalObig((log d)fracalpha+12Tfrac1-alpha2+log Tbig)$をミニマックス下界として証明する。
第2に,汎用的なアッパー信頼境界(UCB)戦略に着想を得た,シンプルで効率的なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-09-23T19:35:38Z) - Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy [71.17938026619068]
我々は、腕の総数が膨大であることができるトップ$ k$極端な文脈的包帯問題を研究します。
まず,Inverse Gap Weighting戦略を用いて,非極端に実現可能な設定のアルゴリズムを提案する。
我々のアルゴリズムは、$O(ksqrt(A-k+1)T log (|mathcalF|T))$である。
論文 参考訳（メタデータ） (2021-02-15T19:10:52Z) - Doubly robust Thompson sampling for linear payoffs [12.375561840897742]
本稿では,Douubly Robust (DR) Thompson Sampling と呼ばれる新しいマルチアームコンテキスト帯域幅アルゴリズムを提案する。
提案アルゴリズムは, 新たな補遺分解を許容し, $tildeO(phi-2sqrtT)$の順序で補遺を改良する。
論文 参考訳（メタデータ） (2021-02-01T23:31:10Z) - Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits
with Linear Payoff Functions [53.77572276969548]
我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。
一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-20T04:29:18Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z) - Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。
最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
論文 参考訳（メタデータ） (2020-03-04T07:36:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。