論文の概要: Low-Rank Generalized Linear Bandit Problems
- arxiv url: http://arxiv.org/abs/2006.02948v2
- Date: Mon, 19 Oct 2020 17:52:43 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-25 09:24:13.719315
- Title: Low-Rank Generalized Linear Bandit Problems
- Title（参考訳）: 低ランク一般化線形帯域問題
- Authors: Yangyi Lu, Amirhossein Meisami, Ambuj Tewari
- Abstract要約: 低ランク線型バンドイット問題において、作用の報酬は、作用と未知の低ランク行列$Theta*$の間の内部積である。
低ランク行列の被覆によって構築される指数重み付き平均予測器と、オンラインから信頼度セットへの変換パバシ2012onlineの新たな組み合わせに基づくアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 19.052901817304743
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In a low-rank linear bandit problem, the reward of an action (represented by
a matrix of size $d_1 \times d_2$) is the inner product between the action and
an unknown low-rank matrix $\Theta^*$. We propose an algorithm based on a novel
combination of online-to-confidence-set conversion~\citep{abbasi2012online} and
the exponentially weighted average forecaster constructed by a covering of
low-rank matrices. In $T$ rounds, our algorithm achieves
$\widetilde{O}((d_1+d_2)^{3/2}\sqrt{rT})$ regret that improves upon the
standard linear bandit regret bound of $\widetilde{O}(d_1d_2\sqrt{T})$ when the
rank of $\Theta^*$: $r \ll \min\{d_1,d_2\}$. We also extend our algorithmic
approach to the generalized linear setting to get an algorithm which enjoys a
similar bound under regularity conditions on the link function. To get around
the computational intractability of covering based approaches, we propose an
efficient algorithm by extending the "Explore-Subspace-Then-Refine" algorithm
of~\citet{jun2019bilinear}. Our efficient algorithm achieves
$\widetilde{O}((d_1+d_2)^{3/2}\sqrt{rT})$ regret under a mild condition on the
action set $\mathcal{X}$ and the $r$-th singular value of $\Theta^*$. Our upper
bounds match the conjectured lower bound of \cite{jun2019bilinear} for a
subclass of low-rank linear bandit problems. Further, we show that existing
lower bounds for the sparse linear bandit problem strongly suggest that our
regret bounds are unimprovable. To complement our theoretical contributions, we
also conduct experiments to demonstrate that our algorithm can greatly
outperform the performance of the standard linear bandit approach when
$\Theta^*$ is low-rank.
- Abstract（参考訳）: 低ランク線形バンディット問題において、作用の報酬(d_1 \times d_2$ の大きさの行列で表される)は作用と未知の低ランク行列 $\theta^*$ との間の内積である。
そこで本研究では,オンラインからセットへの変換〜\citep{abbasi2012online}と指数重み付け平均予測器を組み合わせたアルゴリズムを提案する。
t$ ラウンドにおいて、このアルゴリズムは$\theta^*$: $r \ll \min\{d_1,d_2\}$のときに$\widetilde{o}((d_1+d_2)^{3/2}\sqrt{rt})$を成し、標準的な線形バンドイットの後悔を$\widetilde{o}(d_1d_2\sqrt{t})$とする。
また,本手法を一般化線形設定に拡張し,リンク関数上の正規性条件下で同様の境界を享受するアルゴリズムを得る。
カバーベースアプローチの計算の難解性を回避するために,~\citet{jun2019bilinear}の"explore-subspace-then-refine"アルゴリズムを拡張し,効率的なアルゴリズムを提案する。
我々の効率的なアルゴリズムは、アクションセット$\mathcal{X}$と$\Theta^*$の$r$-th特異値に対する穏やかな条件下で、$\widetilde{O}((d_1+d_2)^{3/2}\sqrt{rT})$ regretを達成する。
我々の上界は、低ランク線型バンディット問題のサブクラスに対する \cite{jun2019bilinear} の予想下界と一致する。
さらに,スパース線形バンディット問題に対する既存の下限は,我々の後悔の限界が改善不可能であることを強く示唆する。
また,理論的な貢献を補完するために,$\Theta^*$が低ランクである場合に,我々のアルゴリズムが標準線形帯域法の性能を大幅に上回ることを示す実験を行った。
関連論文リスト
- Low-rank Matrix Bandits with Heavy-tailed Rewards [55.03293214439741]
アンダーライン重み付きアンダーラインリワード(LowHTR)を用いたアンダーラインローランク行列バンディットの問題点について検討する。
観測されたペイオフに対するトランケーションと動的探索を利用して,LOTUSと呼ばれる新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-04-26T21:54:31Z) - Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery [45.601316850669406]
本稿では,政策評価,最良政策識別,後悔の最小化のための効率的なアルゴリズムを提案する。
政策評価と最良の政策識別のために,我々のアルゴリズムは最小限に最適であることを示す。
提案アルゴリズムは、まずスペクトル法を利用して、低ランク報酬行列の左特異部分空間と右特異部分空間を推定する。
論文 参考訳（メタデータ） (2024-02-24T06:36:08Z) - Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
一般化線形モデル (GLM) フレームワークを用いて, citelu2021low で提案した一般化低ランク行列帯域問題について検討する。
既存のアルゴリズムの計算不可能性と理論的制約を克服するため,まずG-ESTTフレームワークを提案する。
G-ESTT は $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret を達成でき、G-ESTS は $tildeO を達成できることを示す。
論文 参考訳（メタデータ） (2024-01-14T14:14:19Z) - Best-of-Both-Worlds Algorithms for Linear Contextual Bandits [11.94312915280916]
両世界のベスト・オブ・ワールドズ・アルゴリズムを$K$武器付き線形文脈包帯に対して検討する。
我々のアルゴリズムは、敵対的体制と敵対的体制の両方において、ほぼ最適の後悔の限界を提供する。
論文 参考訳（メタデータ） (2023-12-24T08:27:30Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - 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) - Impact of Representation Learning in Linear Bandits [83.17684841392754]
本研究では,表現学習が帯域幅問題の効率性を向上させる方法について検討する。
我々は,$widetildeO(TsqrtkN + sqrtdkNT)$ regretを達成する新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-10-13T16:35:30Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z) - Problem-Complexity Adaptive Model Selection for Stochastic Linear
Bandits [20.207989166682832]
2つの一般的な線形バンディット設定におけるモデル選択の問題について考察する。
まず、[K]$におけるarm $iの平均的な報酬は、$mu_i+ langle alpha_i,t,theta*|$である。
我々は、ALBが$O(|theta*|sqrtT)$の後悔のスケーリングを達成することを示す。
論文 参考訳（メタデータ） (2020-06-04T02:19:00Z) - Efficient and Robust Algorithms for Adversarial Linear Contextual
Bandits [13.32560004325655]
古典的な$K$武器の線形文脈包帯問題の逆変法を考える。
$d$-dimensionalコンテキストがランダムに生成されるという仮定の下で、古典的なExp3アルゴリズムに基づいて効率的なアルゴリズムを開発する。
論文 参考訳（メタデータ） (2020-02-01T22:49:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。