VO$Q$L: Towards Optimal Regret in Model-free RL with Nonlinear Function Approximation
원문 초록
We study time-inhomogeneous episodic reinforcement learning (RL) under general function approximation and sparse rewards. We design a new algorithm, Variance-weighted Optimistic $Q$-Learning (VO$Q$L), based on $Q$-learning and bound its regret assuming completeness and bounded Eluder dimension for the regression function class. As a special case, VO$Q$L achieves $\tilde{O}(d\sqrt{HT}+d^6H^{5})$ regret over $T$ episodes for a horizon $H$ MDP under ($d$-dimensional) linear function approximation, which is asymptotically optimal. Our algorithm incorporates weighted regression-based upper and lower bounds on the optimal value function to obtain this improved regret. The algorithm is computationally efficient given a regression oracle over the function class, making this the first computationally tractable and statistically optimal approach for linear MDPs.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
비동기 Q-러닝에 대한 도달 시간 경계
Hitting-Time Bounds for Asynchronous Q-Learning
우리는 유한 마르코프 결정 과정(Markov decision process)의 단일 궤적(trajectory)으로부터 표준 비동기 Q-러닝의 마지막 반복값(last iterate)을 연구한다. 이 궤적은 상태-행동 연쇄(state-action chain)가 기약적(irreducible)이고 주기적(periodic)일 수 있는 고정된 행동 정책(behavior policy)을 따른다. 할인율(discount factor) $γ$에 대해 $H=(1-γ)^{-1}$로 표기하고, $μ_{\min}$을 최소 정상 상태-행동 확률(stationary state-action probability), $\mathfrak h_\star$를 역방향 상태-행동 연쇄의 최대 기대 적중 시간(hitting time)으로 정의한다. 우리는 $0<\varepsilon\le1$에 대해, 상수 스텝 크기(step size)를 사용하는 0으로 초기화된 Q-러닝이 $\widetilde{O}(H^4/(μ_{\min}\varepsilon^2)+\mathfrak h_\star)$개의 전이(transition)를 사용하여 높은 확률로 최대 $\varepsilon$의 sup-노름(sup-norm) 오차를 달성함을 증명한다. 통계적 항은 표준 Q-러닝의 4차 유효 지평(effective horizon) 의존성을 그대로 유지하며, 초기화 비용은 $\mathfrak h_\star$에 가산적으로 더해진다. 비주기적(aperiodic) 행동 연쇄의 경우, 혼합 시간(mixing time)과의 비교를 통해 $\widetilde{O}(t_{\mathrm{mix}}/μ_{\min})$의 과도 항(transient term)을 얻는다. 경험적 상태-행동 카운트 규칙(empirical state-action count rule)은 이후의 학습 실행(training run)을 위한 상수 스텝 크기를 선택하며, 모델 매개변수, 목표 정확도, 신뢰 수준에 대한 사전 지식 없이도 동일한 비율을 달성한다. 출력값은 마지막 학습 반복값이며, 두 단계 모두 샘플 수에 포함된다. 증명은 두 개의 결정론적 벨만 외피(Bellman envelope)를 사용하여 통계적 오차와 고정 정책 초기화 오차를 분리하며, TD 학습(TD learning)의 역시간 적중 비용 보정(reverse-time hitting-cost compensation)을 상태-행동 전파(state-action propagation)에 맞게 적용한다. 임의의 예측 가능한(predictable) 스텝 크기에 대해 탐험(exploration) 하한이 성립한다. 기존의 통계적 하한 및 파일럿으로 선택된 상수 스텝으로의 확장과 결합하면, 명시된 대규모 샘플 매개변수(parameter) 클래스에서 로그 인자(logarithmic factor)까지 일치하는 평균제곱 비율(mean-square rate)을 얻는다.
PGDQN: Preference-Guided Deep Q-Network
Task Independent Capsule-Based Agents for Deep Q-Learning
Variation-resistant Q-learning: Controlling and Utilizing Estimation Bias in Reinforcement Learning for Better Performance
Robust Multi-Agent Reinforcement Learning with Model Uncertainty
Deep Reinforcement Learning Based Power Allocation for D2D Network
토론
이 논문과 연결된 포럼 글이 아직 없습니다.