論文の概要: Improved Space Bounds for Learning with Experts
- arxiv url: http://arxiv.org/abs/2303.01453v1
- Date: Thu, 2 Mar 2023 18:11:39 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-03 13:05:45.697692
- Title: Improved Space Bounds for Learning with Experts
- Title（参考訳）: 専門家による学習のための空間境界の改善
- Authors: Anders Aamand, Justin Y. Chen, Huy L\^e Nguyen, and Sandeep Silwal
- Abstract要約: スペース予算が$ndelta$ for $delta in (0,1)$であるなら、後悔すべき$tildeO(n2 T1/ (1+delta))$を達成するアルゴリズムを提供する。
この改善は、我々のアルゴリズムの後悔が $tildeO_n(sqrtT)$ に近づくレシエーション $delta rightarrow 1$ において特に有益である。
- 参考スコア（独自算出の注目度）: 5.348126792695619
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We give improved tradeoffs between space and regret for the online learning
with expert advice problem over $T$ days with $n$ experts. Given a space budget
of $n^{\delta}$ for $\delta \in (0,1)$, we provide an algorithm achieving
regret $\tilde{O}(n^2 T^{1/(1+\delta)})$, improving upon the regret bound
$\tilde{O}(n^2 T^{2/(2+\delta)})$ in the recent work of [PZ23]. The improvement
is particularly salient in the regime $\delta \rightarrow 1$ where the regret
of our algorithm approaches $\tilde{O}_n(\sqrt{T})$, matching the $T$
dependence in the standard online setting without space restrictions.
- Abstract（参考訳）: 私たちは空間間のトレードオフを改善し、専門家のアドバイスでオンライン学習に後悔しています。
空間予算が$n^{\delta}$ for $\delta \in (0,1)$を与えられた場合、[PZ23] の最近の研究において、後悔すべき$\tilde{O}(n^2 T^{1/(1+\delta)})$に対して、後悔すべき$\tilde{O}(n^2 T^{2/(2+\delta)})$を改善するアルゴリズムを提供する。
この改善は、我々のアルゴリズムの後悔が、スペース制限のない標準オンライン設定における$T$依存と一致する$\tilde{O}_n(\sqrt{T})$に近づく体制において特に有益である。
関連論文リスト
- Fully Unconstrained Online Learning [45.31874270358511]
G$-Lipschitz convexの損失に対して、後悔する$G|w_star|sqrtTlog(|w_star|GsqrtT) + |w_star|2 + G2$を得るオンライン学習アルゴリズムを提供する。
論文 参考訳（メタデータ） (2024-05-30T23:41:01Z) - Low-rank Matrix Bandits with Heavy-tailed Rewards [55.03293214439741]
アンダーライン重み付きアンダーラインリワード(LowHTR)を用いたアンダーラインローランク行列バンディットの問題点について検討する。
観測されたペイオフに対するトランケーションと動的探索を利用して,LOTUSと呼ばれる新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-04-26T21:54:31Z) - On the Minimax Regret for Online Learning with Feedback Graphs [5.721380617450645]
強く観察可能な無向フィードバックグラフを用いて,オンライン学習を後悔する上で,上層と下層の境界を改善した。
改良された上界$mathcalObigl(sqrtalpha T(ln K)/(lnalpha)bigr)$ hold for any $alpha$ and the lower bounds for bandits and experts。
論文 参考訳（メタデータ） (2023-05-24T17:40:57Z) - Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。
我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。
技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
論文 参考訳（メタデータ） (2022-10-15T09:22:22Z) - Logarithmic Regret from Sublinear Hints [76.87432703516942]
自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。
また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
論文 参考訳（メタデータ） (2021-11-09T16:50:18Z) - Nearly Horizon-Free Offline Reinforcement Learning [97.36751930393245]
S$状態、$A$アクション、計画的地平$H$で、エピソードな時間同質なMarkov決定プロセスに関するオフライン強化学習を再考する。
経験的MDPを用いた評価と計画のための,約$H$自由なサンプル複雑性境界の最初の集合を得る。
論文 参考訳（メタデータ） (2021-03-25T18:52:17Z) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳（メタデータ） (2021-02-15T08:16:51Z) - $Q$-learning with Logarithmic Regret [60.24952657636464]
楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
論文 参考訳（メタデータ） (2020-06-16T13:01:33Z) - Adaptive Online Learning with Varying Norms [45.11667443216861]
オンライン凸最適化アルゴリズムは、あるドメインで$w_t$を出力する。
この結果を用いて新しい「完全行列」型後悔境界を得る。
論文 参考訳（メタデータ） (2020-02-10T17:22:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。