論文の概要: Tiered Reinforcement Learning: Pessimism in the Face of Uncertainty and
Constant Regret
- arxiv url: http://arxiv.org/abs/2205.12418v1
- Date: Wed, 25 May 2022 00:03:25 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-26 12:31:39.150961
- Title: Tiered Reinforcement Learning: Pessimism in the Face of Uncertainty and
Constant Regret
- Title（参考訳）: 階層的強化学習:不確実性と絶え間ない後悔に直面した悲観主義
- Authors: Jiawei Huang, Li Zhao, Tao Qin, Wei Chen, Nan Jiang, Tie-Yan Liu
- Abstract要約: 実世界のユーザインタラクションアプリケーションの階層構造をキャプチャする新しい学習フレームワークを提案する。
同時に、$pitextO$と$pitextE$の2つのポリシーを保持します。
Pessimistic Value It を $pitextE$ の生成アルゴリズムとして選択すれば,リスク回避ユーザに対して常に後悔の念を抱くことができることを示す。
- 参考スコア（独自算出の注目度）: 144.06550139857296
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose a new learning framework that captures the tiered structure of
many real-world user-interaction applications, where the users can be divided
into two groups based on their different tolerance on exploration risks and
should be treated separately. In this setting, we simultaneously maintain two
policies $\pi^{\text{O}}$ and $\pi^{\text{E}}$: $\pi^{\text{O}}$ ("O" for
"online") interacts with more risk-tolerant users from the first tier and
minimizes regret by balancing exploration and exploitation as usual, while
$\pi^{\text{E}}$ ("E" for "exploit") exclusively focuses on exploitation for
risk-averse users from the second tier utilizing the data collected so far. An
important question is whether such a separation yields advantages over the
standard online setting (i.e., $\pi^{\text{E}}=\pi^{\text{O}}$) for the
risk-averse users. We individually consider the gap-independent
vs.~gap-dependent settings. For the former, we prove that the separation is
indeed not beneficial from a minimax perspective. For the latter, we show that
if choosing Pessimistic Value Iteration as the exploitation algorithm to
produce $\pi^{\text{E}}$, we can achieve a constant regret for risk-averse
users independent of the number of episodes $K$, which is in sharp contrast to
the $\Omega(\log K)$ regret for any online RL algorithms in the same setting,
while the regret of $\pi^{\text{O}}$ (almost) maintains its online regret
optimality and does not need to compromise for the success of $\pi^{\text{E}}$.
- Abstract（参考訳）: 本研究では,多くの現実世界のユーザインタラクションアプリケーションの階層構造を抽出し,探索リスクに対する耐性の異なる2つのグループに分割し,個別に扱うことができる新しい学習フレームワークを提案する。
この設定では、2つのポリシーを同時に維持します。 $\pi^{\text{O}}$と$\pi^{\text{E}}$: $\pi^{\text{O}}$ ("O" for "オンライン")は、第一層からのよりリスク耐性のあるユーザと対話し、通常通り探索とエクスプロイトのバランスをとることで後悔を最小限にします。
重要な疑問は、そのような分離が標準のオンライン設定(例えば $\pi^{\text{E}}=\pi^{\text{O}}$)に対してリスク-逆ユーザに対して利点をもたらすかどうかである。
ギャップ非依存 vs を個別に検討する。
〜gap依存設定。
前者にとって、分離がミニマックスの観点からは有益でないことが証明される。
後者の場合、Pessimistic Value Iteration を $\pi^{\text{E}}$ の生成アルゴリズムとして選んだ場合、$K$ は、同じ設定のオンライン RL アルゴリズムでは $\Omega(\log K)$ の後悔とは対照的に、$\pi^{\text{O}}$ の後悔はオンラインの後悔の最適性を維持し、$\pi^{\text{E}}$ の成功には妥協する必要がない。
関連論文リスト
- Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaR [58.40575099910538]
本研究は,リスク許容度が$tau$のCVaR(Conditional Value at Risk)の目的に着目し,リスクに敏感な強化学習(RL)について検討する。
ミニマックスCVaRの後悔率は$Omega(sqrttau-1AK)$で、$A$はアクションの数、$K$はエピソード数である。
我々は,このアルゴリズムが連続性仮定の下で$widetilde O(tau-1sqrtSAK)$の最適後悔を達成し,一般に近似することを示す。
論文 参考訳（メタデータ） (2023-02-07T02:22:31Z) - Private Online Prediction from Experts: Separations and Faster Rates [74.52487417350221]
専門家によるオンライン予測は機械学習の基本的な問題であり、いくつかの研究がプライバシーの制約の下でこの問題を研究している。
本研究では,非適応的敵に対する最良な既存アルゴリズムの残差を克服する新たなアルゴリズムを提案し,解析する。
論文 参考訳（メタデータ） (2022-10-24T18:40:19Z) - Coordinated Attacks against Contextual Bandits: Fundamental Limits and
Defense Mechanisms [75.17357040707347]
オンラインレコメンデーションシステムによってモチベーションされた我々は,文脈的包帯における最適政策の発見問題を提案する。
目標は、優れたユーザに対する報酬を可能な限り少ないユーザインタラクションで最大化するポリシーを、しっかりと学習することだ。
効率的なロバストな平均推定器を用いることで、$tildeO(min(S,A)cdot alpha/epsilon2)$ upper-boundを実現できることを示す。
論文 参考訳（メタデータ） (2022-01-30T01:45:13Z) - Gap-Dependent Unsupervised Exploration for Reinforcement Learning [40.990467706237396]
タスクに依存しない強化学習のための効率的なアルゴリズムを提案する。
このアルゴリズムは1/epsilon cdot (H3SA / rho + H4 S2 A) の$widetildemathcalOのみを探索する。
情報理論上、この境界は$rho Theta (1/(HS))$と$H>1$に対してほぼ厳密であることを示す。
論文 参考訳（メタデータ） (2021-08-11T20:42:46Z) - Near-Optimal Algorithms for Differentially Private Online Learning in a Stochastic Environment [7.4288915613206505]
本研究では,バンディットとフルインフォメーションの両方のフィードバックの下で,オンライン学習環境における個人差分問題について検討する。
差分的な私的盗賊に対しては、UTBとトンプソンサンプリングに基づくアルゴリズムを同時に提案し、最適な$O左(sum_j: Delta_j>0 fracln(T)min leftDelta_j, epsilon right)$ minimax lower boundとする。
同じ差分プライベートなフル情報設定に対しては、$epsilon$-differentially も提示する。
論文 参考訳（メタデータ） (2021-02-16T02:48:16Z) - Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive
Multi-Step Bootstrap [84.66885506098724]
本稿では,アダプティブ・マルチステップ・ブートストラップ (AMB) を用いた表層有限水平マルコフ決定過程 (MDP) のモデルフリーアルゴリズムを提案する。
AMBは,部分最適ギャップの逆の和でのみスケールする,ギャップ依存的後悔境界を達成できることを示す。
また、AMB は $frac|Z_mul|Delta_min$ regret という追加の $frac|Z_mul|Delta_min$ を被っていることも示しています。
論文 参考訳（メタデータ） (2021-02-09T07:46:34Z) - Minimax Regret for Stochastic Shortest Path with Adversarial Costs and
Known Transition [37.6975819766632]
我々は、敵対コストと既知の移行で最短経路問題を研究します。
ミニマックスの後悔は,全情報設定と盗聴フィードバック設定に対して$widetildeO(sqrtDTstar K)$および$widetildeO(sqrtDTstar SA K)$であることを示す。
論文 参考訳（メタデータ） (2020-12-07T20:55:28Z) - Accommodating Picky Customers: Regret Bound and Exploration Complexity
for Multi-Objective Reinforcement Learning [43.75491612671571]
目的と目的のバランスをとる多目的強化学習について、好みを用いて検討する。
我々はこの問題をマルコフ決定過程における叙述的学習問題として定式化する。
モデルに基づくアルゴリズムは、最小限の最小限のリセットを$widetildemathcalObigl(sqrtmind,Scdot H3 SA/epsilon2bigr)$とする。
論文 参考訳（メタデータ） (2020-11-25T21:45:04Z) - Risk-Sensitive Reinforcement Learning: Near-Optimal Risk-Sample Tradeoff
in Regret [115.85354306623368]
本研究では,未知の遷移カーネルを持つマルコフ決定過程におけるリスク感応性強化学習について検討する。
確率的に効率的なモデルレスアルゴリズムとして、リスク感性価値反復(RSVI)とリスク感性Q-ラーニング(RSQ)を提案する。
RSVIが $tildeObig(lambda(|beta| H2) cdot sqrtH3 S2AT big) に達したことを証明しています。
論文 参考訳（メタデータ） (2020-06-22T19:28:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。