論文の概要: Beyond Task Diversity: Provable Representation Transfer for Sequential Multi-Task Linear Bandits

• arxiv url: http://arxiv.org/abs/2501.13390v1
• Date: Thu, 23 Jan 2025 05:21:27 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-24 15:57:43.845602
• Title: Beyond Task Diversity: Provable Representation Transfer for Sequential Multi-Task Linear Bandits
• Title（参考訳）: タスクの多様性を超えて:連続多タスク線形帯域の確率的表現伝達
• Authors: Thang Duong, Zhi Wang, Chicheng Zhang,
• Abstract要約: 本研究では,線形バンディットにおける生涯学習について研究し,そこでは学習者が一連の線形バンディットタスクと対話する。 現在の文献では、これらのタスクは多様であり、例えば、それらのパラメータは$m$次元の部分空間に一様に存在すると仮定している。 タスクの多様性を仮定せずに連続したマルチタスク線形帯域に対する最初の非自明な結果を示す。
• 参考スコア（独自算出の注目度）: 17.970177214029473
• License:
• Abstract: We study lifelong learning in linear bandits, where a learner interacts with a sequence of linear bandit tasks whose parameters lie in an $m$-dimensional subspace of $\mathbb{R}^d$, thereby sharing a low-rank representation. Current literature typically assumes that the tasks are diverse, i.e., their parameters uniformly span the $m$-dimensional subspace. This assumption allows the low-rank representation to be learned before all tasks are revealed, which can be unrealistic in real-world applications. In this work, we present the first nontrivial result for sequential multi-task linear bandits without the task diversity assumption. We develop an algorithm that efficiently learns and transfers low-rank representations. When facing $N$ tasks, each played over $\tau$ rounds, our algorithm achieves a regret guarantee of $\tilde{O}\big (Nm \sqrt{\tau} + N^{\frac{2}{3}} \tau^{\frac{2}{3}} d m^{\frac13} + Nd^2 + \tau m d \big)$ under the ellipsoid action set assumption. This result can significantly improve upon the baseline of $\tilde{O} \left (Nd \sqrt{\tau}\right)$ that does not leverage the low-rank structure when the number of tasks $N$ is sufficiently large and $m \ll d$. We also demonstrate empirically on synthetic data that our algorithm outperforms baseline algorithms, which rely on the task diversity assumption.
• Abstract（参考訳）: そこで,学習者は,$\mathbb{R}^d$の$m$次元部分空間にパラメータを配置した線形バンドイットタスクの列と相互作用し,低ランク表現を共有する。 現在の文献では、これらのタスクは多様であり、例えば、それらのパラメータは$m$-次元の部分空間に一様に存在すると仮定している。 この仮定により、全てのタスクが明らかにされる前に低ランク表現を学習することができ、これは現実世界のアプリケーションでは非現実的である。 本研究では,タスクの多様性を仮定せずに連続マルチタスク線形帯域に対する最初の非自明な結果を示す。 低ランク表現を効率的に学習し、転送するアルゴリズムを開発した。 N$タスクに直面して、それぞれ$\tau$ラウンドでプレイすると、楕円体アクションセットの仮定の下で、我々のアルゴリズムは、$\tilde{O}\big (Nm \sqrt{\tau} + N^{\frac{2}{3}} \tau^{\frac{2}{3}} d m^{\frac13} + Nd^2 + \tau m d \big)$の後悔の保証を達成する。 この結果は$\tilde{O} \left (Nd \sqrt{\tau}\right)$のベースラインで大幅に改善される。 また,アルゴリズムがタスクの多様性の仮定に依存するベースラインアルゴリズムより優れている合成データについても実証実験を行った。

関連論文リスト

• Scaling Distributed Multi-task Reinforcement Learning with Experience Sharing [38.883540444516605]
  DARPAはShELLプログラムを立ち上げた。これは、経験共有が分散生涯学習エージェントにどのように役立つかを探求することを目的としている。 分散マルチタスク強化学習(RL)の理論的および実証的研究を行い、N$エージェントのグループがM$タスクを協調的に解決する。 我々はDistMT-LSVIと呼ばれるアルゴリズムを提案し、各エージェントは独立に$epsilon$-optimal Policyを全ての$M$タスクに対して学習する。
  論文  参考訳（メタデータ） (2023-07-11T22:58:53Z)
• Simplifying and Understanding State Space Models with Diagonal Linear RNNs [56.33053691749856]
  本研究は、離散化ステップを解消し、バニラ対角線形RNNに基づくモデルを提案する。 概念的にはるかに単純であるにもかかわらず、$mathrmDLR$は以前提案したSSMと同じくらいのパフォーマンスを示す。 また、合成シーケンス・ツー・シーケンス・タスクのスイートによって、SSMとアテンションベースモデルの表現性も特徴付ける。
  論文  参考訳（メタデータ） (2022-12-01T18:53:06Z)
• Nearly Minimax Algorithms for Linear Bandits with Shared Representation [86.79657561369397]
  我々は、次元が$d$で、それぞれ$T$のラウンドで$M$リニアバンディットをプレイする設定を考え、これらの$M$リニアバンディットタスクは共通の$k(ll d)$次元リニア表現を共有する。 我々は$widetildeOleft(dsqrtkMT + kMsqrtTright)$ regret boundsを達成する新しいアルゴリズムを考案した。
  論文  参考訳（メタデータ） (2022-03-29T15:27:13Z)
• Multi-task Representation Learning with Stochastic Linear Bandits [29.8208189270894]
  線形バンディットタスクの設定におけるトランスファーラーニングの問題について検討する。 我々は,タスク間で低次元線形表現が共有されていると考え,マルチタスク学習環境において,この表現を学習するメリットについて検討する。
  論文  参考訳（メタデータ） (2022-02-21T09:26:34Z)
• Provable Lifelong Learning of Representations [21.440845049501778]
  そこで本研究では,内部特徴表現を保守・洗練する,証明可能な生涯学習アルゴリズムを提案する。 すべてのタスクにおける任意の所望の精度に対して、表現の次元は、基礎となる表現の次元に近いままであることを示す。
  論文  参考訳（メタデータ） (2021-10-27T00:41:23Z)
• On the Power of Multitask Representation Learning in Linear MDP [61.58929164172968]
  本稿では,線形マルコフ決定過程(MDP)におけるマルチタスク表現学習の統計的メリットについて分析する。 簡単な最小二乗アルゴリズムが $tildeO(H2sqrtfrackappa MathcalC(Phi)2 kappa dNT+frackappa dn) というポリシーを学ぶことを証明した。
  論文  参考訳（メタデータ） (2021-06-15T11:21:06Z)
• Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
  我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。 実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
  論文  参考訳（メタデータ） (2021-05-17T16:40:48Z)
• Near-optimal Representation Learning for Linear Bandits and Linear RL [41.33483293243257]
  私たちはまず、次元が$d$の線形バンディットを同時に$M$で演奏する設定を考えます。 これらの包帯は、$k$-次元線型表現を共有するので、$kll d$ と $k ll M$ が成り立つ。 我々は、共有表現を利用して$tildeO(MsqrtdkT + dsqrtkMT )を後悔するサンプル効率のアルゴリズムMTLR-OFULを提案する。
  論文  参考訳（メタデータ） (2021-02-08T11:11:53Z)
• Impact of Representation Learning in Linear Bandits [83.17684841392754]
  本研究では,表現学習が帯域幅問題の効率性を向上させる方法について検討する。 我々は,$widetildeO(TsqrtkN + sqrtdkNT)$ regretを達成する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-10-13T16:35:30Z)
• Few-Shot Learning via Learning the Representation, Provably [115.7367053639605]
  本稿では,表現学習による少数ショット学習について検討する。 1つのタスクは、ターゲットタスクのサンプルの複雑さを減らすために、$T$ソースタスクと$n_1$データを使用して表現を学習する。
  論文  参考訳（メタデータ） (2020-02-21T17:30:00Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。