論文の概要: Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems
- arxiv url: http://arxiv.org/abs/2401.07298v1
- Date: Sun, 14 Jan 2024 14:14:19 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-17 18:56:36.579781
- Title: Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems
- Title（参考訳）: 一般化低ランク行列帯域問題のための効率的なフレームワーク
- Authors: Yue Kang, Cho-Jui Hsieh, Thomas C. M. Lee
- Abstract要約: 一般化線形モデル (GLM) フレームワークを用いて, citelu2021low で提案した一般化低ランク行列帯域問題について検討する。
既存のアルゴリズムの計算不可能性と理論的制約を克服するため,まずG-ESTTフレームワークを提案する。
G-ESTT は $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret を達成でき、G-ESTS は $tildeO を達成できることを示す。
- 参考スコア（独自算出の注目度）: 61.85150061213987
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In the stochastic contextual low-rank matrix bandit problem, the expected
reward of an action is given by the inner product between the action's feature
matrix and some fixed, but initially unknown $d_1$ by $d_2$ matrix $\Theta^*$
with rank $r \ll \{d_1, d_2\}$, and an agent sequentially takes actions based
on past experience to maximize the cumulative reward. In this paper, we study
the generalized low-rank matrix bandit problem, which has been recently
proposed in \cite{lu2021low} under the Generalized Linear Model (GLM)
framework. To overcome the computational infeasibility and theoretical restrain
of existing algorithms on this problem, we first propose the G-ESTT framework
that modifies the idea from \cite{jun2019bilinear} by using Stein's method on
the subspace estimation and then leverage the estimated subspaces via a
regularization idea. Furthermore, we remarkably improve the efficiency of
G-ESTT by using a novel exclusion idea on the estimated subspace instead, and
propose the G-ESTS framework. We also show that G-ESTT can achieve the
$\tilde{O}(\sqrt{(d_1+d_2)MrT})$ bound of regret while G-ESTS can achineve the
$\tilde{O}(\sqrt{(d_1+d_2)^{3/2}Mr^{3/2}T})$ bound of regret under mild
assumption up to logarithm terms, where $M$ is some problem dependent value.
Under a reasonable assumption that $M = O((d_1+d_2)^2)$ in our problem setting,
the regret of G-ESTT is consistent with the current best regret of
$\tilde{O}((d_1+d_2)^{3/2} \sqrt{rT}/D_{rr})$~\citep{lu2021low} ($D_{rr}$ will
be defined later). For completeness, we conduct experiments to illustrate that
our proposed algorithms, especially G-ESTS, are also computationally tractable
and consistently outperform other state-of-the-art (generalized) linear matrix
bandit methods based on a suite of simulations.
- Abstract（参考訳）: 確率的文脈的低ランク行列バンドイット問題において、アクションの期待された報酬は、アクションの特徴行列と固定されたいくつかの内部積によって与えられるが、最初は未知の$d_1$ by $d_2$ matrix $\Theta^*$ with rank $r \ll \{d_1, d_2\}$で与えられる。
本稿では,一般化線形モデル(GLM)の枠組みの下で,最近 \cite{lu2021low} で提案されている一般化低ランク行列バンドイット問題について検討する。
この問題に対する既存のアルゴリズムの計算不可能性と理論的制約を克服するために,まず,部分空間推定におけるsteinの手法を用いて \cite{jun2019bilinear} のアイデアを修飾した g-estt フレームワークを提案し,その推定部分空間を正規化アイデアで活用する。
さらに,推定部分空間上の新しい排他的概念を用いてG-ESTTの効率を著しく向上させ,G-ESTSフレームワークを提案する。
また、G-ESTT が $\tilde{O}(\sqrt{(d_1+d_2)MrT})$ bound of regret を達成できるのに対し、G-ESTS は $\tilde{O}(\sqrt{(d_1+d_2)^{3/2}Mr^{3/2}T})$ bound of regret を対数的な仮定で達成できる。
M = O(((d_1+d_2)^2)$(d_1+d_2)^2)$ という合理的な仮定の下では、G-ESTT の後悔は $\tilde{O}((d_1+d_2)^{3/2} \sqrt{rT}/D_{rr})$~\citep{lu2021low}$D_{rr}$ の現在の最善後悔と一致する。
完全性のために,提案アルゴリズム,特にG-ESTSは,計算可能であり,一連のシミュレーションに基づいて,他の最先端(一般化)線形行列バンドイット法より一貫して優れていることを示す実験を行う。
関連論文リスト
- LC-Tsallis-INF: Generalized Best-of-Both-Worlds Linear Contextual Bandits [38.41164102066483]
本研究では、独立かつ同一に分散したコンテキストを持つ線形文脈帯域問題について考察する。
提案アルゴリズムは、Tsallisエントロピーを持つFollow-The-Regularized-Leaderに基づいており、$alpha$-textual-Con (LC)-Tsallis-INFと呼ばれている。
論文 参考訳（メタデータ） (2024-03-05T18:59:47Z) - Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery [45.601316850669406]
本稿では,政策評価,最良政策識別,後悔の最小化のための効率的なアルゴリズムを提案する。
政策評価と最良の政策識別のために,我々のアルゴリズムは最小限に最適であることを示す。
提案アルゴリズムは、まずスペクトル法を利用して、低ランク報酬行列の左特異部分空間と右特異部分空間を推定する。
論文 参考訳（メタデータ） (2024-02-24T06:36:08Z) - Best-of-Both-Worlds Algorithms for Linear Contextual Bandits [11.94312915280916]
両世界のベスト・オブ・ワールドズ・アルゴリズムを$K$武器付き線形文脈包帯に対して検討する。
我々のアルゴリズムは、敵対的体制と敵対的体制の両方において、ほぼ最適の後悔の限界を提供する。
論文 参考訳（メタデータ） (2023-12-24T08:27:30Z) - Revisiting Weighted Strategy for Non-stationary Parametric Bandits [82.1942459195896]
本稿では,非定常パラメトリックバンディットの重み付け戦略を再考する。
より単純な重みに基づくアルゴリズムを生成する改良された分析フレームワークを提案する。
我々の新しいフレームワークは、他のパラメトリックバンディットの後悔の限界を改善するのに使える。
論文 参考訳（メタデータ） (2023-03-05T15:11:14Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Thresholded Lasso Bandit [70.17389393497125]
Thresholded Lasso banditは、報酬関数を定義するベクトルとスパースサポートを推定するアルゴリズムである。
一般には $mathcalO( log d + sqrtT )$ や $mathcalO( log d + sqrtT )$ としてスケールする非漸近的後悔の上界を確立する。
論文 参考訳（メタデータ） (2020-10-22T19:14:37Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z) - Low-Rank Generalized Linear Bandit Problems [19.052901817304743]
低ランク線型バンドイット問題において、作用の報酬は、作用と未知の低ランク行列$Theta*$の間の内部積である。
低ランク行列の被覆によって構築される指数重み付き平均予測器と、オンラインから信頼度セットへの変換パバシ2012onlineの新たな組み合わせに基づくアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-04T15:30:14Z) - Naive Exploration is Optimal for Online LQR [49.681825576239355]
最適後悔尺度は$widetildeTheta(sqrtd_mathbfu2 d_mathbfx T)$で、$T$は時間ステップの数、$d_mathbfu$は入力空間の次元、$d_mathbfx$はシステム状態の次元である。
我々の下界は、かつての$mathrmpoly(logT)$-regretアルゴリズムの可能性を排除する。
論文 参考訳（メタデータ） (2020-01-27T03:44:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。