論文の概要: Sample-Efficiency in Multi-Batch Reinforcement Learning: The Need for
Dimension-Dependent Adaptivity
- arxiv url: http://arxiv.org/abs/2310.01616v1
- Date: Mon, 2 Oct 2023 20:14:01 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-04 18:57:51.305851
- Title: Sample-Efficiency in Multi-Batch Reinforcement Learning: The Need for
Dimension-Dependent Adaptivity
- Title（参考訳）: マルチバッチ強化学習におけるサンプル効率:次元依存適応性の必要性
- Authors: Emmeran Johnson, Ciara Pike-Burke, Patrick Rebeschini
- Abstract要約: 強化学習におけるサンプル効率と適応性の関係を理論的に検討する。
私たちは、バッチ毎にフィードバックが処理され、クエリが更新されるように、クエリをK$のバッチで送信できる学習フレームワークを採用しています。
- 参考スコア（独自算出の注目度）: 18.35462792871242
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We theoretically explore the relationship between sample-efficiency and
adaptivity in reinforcement learning. An algorithm is sample-efficient if it
uses a number of queries $n$ to the environment that is polynomial in the
dimension $d$ of the problem. Adaptivity refers to the frequency at which
queries are sent and feedback is processed to update the querying strategy. To
investigate this interplay, we employ a learning framework that allows sending
queries in $K$ batches, with feedback being processed and queries updated after
each batch. This model encompasses the whole adaptivity spectrum, ranging from
non-adaptive 'offline' ($K=1$) to fully adaptive ($K=n$) scenarios, and regimes
in between. For the problems of policy evaluation and best-policy
identification under $d$-dimensional linear function approximation, we
establish $\Omega(\log \log d)$ lower bounds on the number of batches $K$
required for sample-efficient algorithms with $n = O(poly(d))$ queries. Our
results show that just having adaptivity ($K>1$) does not necessarily guarantee
sample-efficiency. Notably, the adaptivity-boundary for sample-efficiency is
not between offline reinforcement learning ($K=1$), where sample-efficiency was
known to not be possible, and adaptive settings. Instead, the boundary lies
between different regimes of adaptivity and depends on the problem dimension.
- Abstract（参考訳）: 強化学習におけるサンプル効率と適応性の関係を理論的に検討する。
アルゴリズムは、問題の次元$d$の多項式である環境に対して、多くのクエリ$n$を使用する場合、サンプリング効率がよい。
適応性とは、クエリが送信され、クエリ戦略を更新するためにフィードバックが処理される頻度を指す。
この相互作用を調べるために、我々は、K$のバッチでクエリを送信できる学習フレームワークを使用し、フィードバックは処理され、各バッチ後にクエリが更新される。
このモデルは、非適応的な「オフライン」(K=1$)から完全に適応的な(K=n$)シナリオまで、適応スペクトル全体を含む。
$d$次元線形関数近似の下での政策評価と最良政治的識別の問題に対して、$n = O(poly(d))$クエリでサンプル効率のアルゴリズムに必要なバッチ数に対して$\Omega(\log \log d)$低い境界を確立する。
その結果,適応性(k>1$)を持つだけではサンプル効率が保証されないことがわかった。
特に、サンプル効率に対する適応性境界は、サンプル効率が不可能であることが判明したオフライン強化学習(K=1$)と適応設定の間にはない。
その代わり、境界は異なる適応性の体系の間にあり、問題次元に依存する。
関連論文リスト
- Stochastic Optimization Algorithms for Instrumental Variable Regression with Streaming Data [17.657917523817243]
この問題を条件付き最適化問題とみなして,器用変分回帰のためのアルゴリズムを開発し,解析する。
最小二乗変数回帰の文脈では、我々のアルゴリズムは行列逆転やミニバッチを必要としない。
任意の$iota>0$に対して$mathcalO(log T/T)$と$mathcalO(1/T1-iota)$の順の収束率を導出する。
論文 参考訳（メタデータ） (2024-05-29T19:21:55Z) - Adaptivity Complexity for Causal Graph Discovery [7.424262881242935]
本稿では,アルゴリズム設計者が合計$r$連続ラウンドで因果グラフを復元する,$r$適応性の問題を考察する。
我々は、検証数に関して$O(minr,log n cdot n1/minr,log n)$近似を達成する$r$適応アルゴリズムを提供する。
論文 参考訳（メタデータ） (2023-06-09T09:49:16Z) - Adaptive Stochastic Gradient Descent for Fast and
Communication-Efficient Distributed Learning [33.590006101071765]
マスタが分散降下(SGD)アルゴリズムを$n$ワーカー上で実行したい場合について検討する。
本研究では,分散SGDの適応バージョンが非適応実装と比較して少ない時間で低い誤差値に達することを示す。
論文 参考訳（メタデータ） (2022-08-04T10:57:25Z) - An Experimental Design Perspective on Model-Based Reinforcement Learning [73.37942845983417]
環境からの状態遷移を観察するのは費用がかかる。
標準RLアルゴリズムは通常、学習するために多くの観測を必要とする。
本稿では,マルコフ決定過程について,状態-作用対がどの程度の情報を提供するかを定量化する獲得関数を提案する。
論文 参考訳（メタデータ） (2021-12-09T23:13:57Z) - How to Query An Oracle? Efficient Strategies to Label Data [59.89900843097016]
機械学習におけるデータセットのラベル付けに専門家の託宣を照会する際の基本的な問題について考察する。
本稿では,サンプルをラベル付けするために,ラウンド・バイ・ラウンドでランダム化されたバッチアルゴリズムを提案し,クエリレートが$O(fracNk2)$であることを示す。
さらに,適応型グリージークエリ方式を提案し,三重項クエリを用いたサンプルあたり平均$approx 0.2N$クエリを実現する。
論文 参考訳（メタデータ） (2021-10-05T20:15:35Z) - AdaGDA: Faster Adaptive Gradient Descent Ascent Methods for Minimax
Optimization [104.96004056928474]
本稿では,非コンケーブ最小値問題に対する高速適応勾配降下法を提案する。
我々は,本手法が,ミニバッチサイズが$O(kappa2.5epsilon-3)$のより低いサンプル複雑性に達することを示す。
論文 参考訳（メタデータ） (2021-06-30T14:47:09Z) - Online Model Selection for Reinforcement Learning with Function
Approximation [50.008542459050155]
我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。
また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
論文 参考訳（メタデータ） (2020-11-19T10:00:54Z) - A No-Free-Lunch Theorem for MultiTask Learning [19.645741778058227]
すべてのタスク$P_t$が共通の最適分類器$h*,$を共有する、一見好都合な分類シナリオを考える。
このようなレジームは、$n$と$N$の両方のミニマックスレートを許容するが、適応アルゴリズムは存在しない。
論文 参考訳（メタデータ） (2020-06-29T03:03:29Z) - FANOK: Knockoffs in Linear Time [73.5154025911318]
本稿では,ガウスモデル-Xノックオフを効率的に実装し,大規模特徴選択問題における誤発見率を制御するアルゴリズムについて述べる。
当社のメソッドは、最大50,000ドルという問題でテストしています。
論文 参考訳（メタデータ） (2020-06-15T21:55:34Z) - Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
カラムサブセット選択、部分空間近似、射影クラスタリング、および空間サブリニアを$n$で使用するターンタイルストリームのボリュームに対する最初の相対エラーアルゴリズムを提供する。
我々の適応的なサンプリング手法は、様々なデータ要約問題に多くの応用をもたらしており、これは最先端を改善するか、より緩和された行列列モデルで以前に研究されただけである。
論文 参考訳（メタデータ） (2020-04-23T05:00:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。