論文の概要: Improved Algorithms for Misspecified Linear Markov Decision Processes
- arxiv url: http://arxiv.org/abs/2109.05546v1
- Date: Sun, 12 Sep 2021 16:02:32 GMT
- ステータス: 処理完了
- システム内更新日: 2021-09-14 16:02:07.880734
- Title: Improved Algorithms for Misspecified Linear Markov Decision Processes
- Title（参考訳）: 不正な線形マルコフ決定過程のアルゴリズムの改良
- Authors: Daniel Vial, Advait Parulekar, Sanjay Shakkottai, R. Srikant
- Abstract要約: 本稿では,不特定線形マルコフ決定過程に対する3つの望ましい特性を持つアルゴリズムを提案する。
提案アルゴリズムは,Sup-Lin-UCBアルゴリズムを一般化し,改良する。
- 参考スコア（独自算出の注目度）: 29.549633678730054
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: For the misspecified linear Markov decision process (MLMDP) model of Jin et
al. [2020], we propose an algorithm with three desirable properties. (P1) Its
regret after $K$ episodes scales as $K \max \{ \varepsilon_{\text{mis}},
\varepsilon_{\text{tol}} \}$, where $\varepsilon_{\text{mis}}$ is the degree of
misspecification and $\varepsilon_{\text{tol}}$ is a user-specified error
tolerance. (P2) Its space and per-episode time complexities remain bounded as
$K \rightarrow \infty$. (P3) It does not require $\varepsilon_{\text{mis}}$ as
input. To our knowledge, this is the first algorithm satisfying all three
properties. For concrete choices of $\varepsilon_{\text{tol}}$, we also improve
existing regret bounds (up to log factors) while achieving either (P2) or (P3)
(existing algorithms satisfy neither). At a high level, our algorithm
generalizes (to MLMDPs) and refines the Sup-Lin-UCB algorithm, which Takemura
et al. [2021] recently showed satisfies (P3) in the contextual bandit setting.
- Abstract（参考訳）: Jinらによる不特定線形マルコフ決定過程(MLMDP)モデルについて。
[2020] では, 3つの望ましい特性を持つアルゴリズムを提案する。
(P1)
k$エピソード後の後悔は、$k \max \{ \varepsilon_{\text{mis}}, \varepsilon_{\text{tol}} \}$であり、$\varepsilon_{\text{mis}}$は誤特定度であり、$\varepsilon_{\text{tol}}$はユーザー指定のエラー許容度である。
(P2)
その空間とエピソード毎の時間複雑性は、$K \rightarrow \infty$として有界である。
(P3)
入力として$\varepsilon_{\text{mis}}$を必要としない。
私たちの知る限り、これは3つの特性をすべて満たす最初のアルゴリズムである。
また、$\varepsilon_{\text{tol}}$の具体的な選択については、(P2) または (P3) を達成しながら、既存の後悔境界(ログファクタまで)を改善します。
高レベルでは,本アルゴリズムは,竹村らが開発したSup-Lin-UCBアルゴリズムを一般化し,洗練する。
[2021]は最近,文脈的帯域設定で満足感(P3)を示した。
関連論文リスト
- Finding good policies in average-reward Markov Decision Processes without prior knowledge [19.89784209009327]
平均回帰決定(MDP)における$varepsilon$-Optimal Policyの同定を再考する。
直径推定法を用いて,$(varepsilon,delta)$-PAC-PACポリシー識別のための最初のアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-05-27T12:24:14Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - Near-Optimal Algorithms for Private Online Optimization in the
Realizable Regime [74.52487417350221]
オンライン学習の問題は,ゼロロスソリューションが存在する,実現可能な環境において考慮する。
そこで我々は,ほぼ最適の後悔境界を求める新たなDPアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-02-27T21:19:24Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - On the complexity of All $\varepsilon$-Best Arms Identification [2.1485350418225244]
ガウスの報酬を持つ有限の多腕バンディットにおいて、$varepsilon$-optimal armsを全て識別する問題を考える。
我々は,$varepsilon$-good arms w.h.p の集合を同定し,期待されるサンプルの複雑さの観点から最適性($delta$が 0 になるとき)を享受するトラック・アンド・ストップアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-02-13T10:54:52Z) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。
損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文 参考訳（メタデータ） (2021-03-02T06:53:44Z) - Differentially Private Online Submodular Maximization [16.422215672356167]
差分プライバシフィード(DP)を用いた基準制約下でのオンラインサブモジュラー関数の問題点について考察する。
共通有限基底集合上の$T$サブモジュラー関数のストリームがオンラインに届き、各時点において、決定者は関数を観察する前に$U$のほとんどの$k$要素を選択する必要がある。
意思決定者は、選択された集合で評価された関数に等しい報酬を得るとともに、期待の低い後悔を実現する一連の集合を学習することを目的とする。
論文 参考訳（メタデータ） (2020-10-24T07:23:30Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳（メタデータ） (2020-06-06T13:34:41Z) - Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast
Algorithm [100.11971836788437]
固定支持ワッサーシュタインバリセンタ問題(FS-WBP)について検討する。
我々は,有望な反復的ブレグマン射影 (IBP) アルゴリズムであるtextscFastIBP の,証明可能な高速なテキスト決定論的変種を開発する。
論文 参考訳（メタデータ） (2020-02-12T03:40:52Z) - Efficient and Robust Algorithms for Adversarial Linear Contextual
Bandits [13.32560004325655]
古典的な$K$武器の線形文脈包帯問題の逆変法を考える。
$d$-dimensionalコンテキストがランダムに生成されるという仮定の下で、古典的なExp3アルゴリズムに基づいて効率的なアルゴリズムを開発する。
論文 参考訳（メタデータ） (2020-02-01T22:49:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。