arXiv:2302.07477v4 cs.LG

안정적 할인 마르코프 결정 과정의 최적 샘플 복잡도

Optimal Sample Complexity of Stable Discounted Markov Decision Processes

Shengbo Wang, Jose Blanchet, Peter Glynn

제출 2023-02-15

한국어 초록

우리는 무한 구간 할인 마르코프 결정 과정(Markov Decision Process)에 대한 표 기반(tabular) 강화학습의 최적 샘플 복잡도를 연구한다. 제약이 없는 최소최대(minimax) 샘플 복잡도는 $\widetilde\Theta((1-\gamma)^{-3}\epsilon^{-2})$로 스케일링되는 것으로 알려져 있으며, 여기서 $\gamma$는 할인 계수(discount factor)를, $\epsilon$은 해의 오차 허용치(solution-error tolerance)를 나타낸다. 그러나 이러한 최악의 경우(worst-case) 비율은 운영 환경에서 흔히 발생하는 안정성 구조를 반영하지 않는다. 분산 감소(variance-reduced) Q-학습 프레임워크를 사용하여, 우리는 추가적인 안정성 가정을 부과하지 않고도 상한노름(sup-norm) Q-함수 추정과 정책 학습 모두 $\widetilde\Theta(H(1-\gamma)^{-2}\epsilon^{-2})$의 선행 샘플 복잡도 의존성을 가짐을 보인다. 여기서 $H=|v^*|_{\mathrm{span}}$은 최적 가치 함수(optimal value function)의 스팬(span)이다. 더 나아가, 모든 정책에 대해 균일한 혼합 시간(mixing time) 상한 $t_{\mathrm{mix}}$을 가정하면, 최적 Q-함수는 $(1-\gamma)^{-1}$과 무관하게 $\widetilde\Theta\left(t_{\mathrm{mix}}^3\epsilon^{-2}\right)$의 샘플 복잡도로 상수 이동(constant shift)까지 추정될 수 있다. 일치하는 하한(matching lower bounds)은 이러한 선행 의존성의 정확성(sharpness)을 입증하며, 추정(estimation)과 제어(control) 사이의 분리(separation)를 드러낸다: Q-함수는 구간(horizon)에 무관한 비율로 가법 상수(additive constant)까지 학습될 수 있지만, 정책 학습은 일반적으로 $(1-\gamma)^{-2}$ 의존성을 그대로 유지한다.

원문 초록

We study the optimal sample complexity of tabular reinforcement learning for infinite-horizon discounted Markov decision processes. The unrestricted minimax sample complexity is known to scale as $\widetilde\Theta((1-\gamma)^{-3}\epsilon^{-2})$, where $\gamma$ denotes the discount factor and $\epsilon$ is the solution-error tolerance. However, this worst-case rate does not account for stability structures that commonly arise in operational environments. Using the variance-reduced Q-learning framework, we show that, without imposing any additional stability assumptions, both sup-norm Q-function estimation and policy learning have leading sample-complexity dependence $\widetilde\Theta(H(1-\gamma)^{-2}\epsilon^{-2})$, where $H=|v^*|_{\mathrm{span}}$ is the span of the optimal value function. Moreover, assuming a uniform mixing time upper bound $t_{\mathrm{mix}}$ over all policies, the optimal Q-function can be estimated up to a constant shift with sample complexity $\widetilde\Theta\left(t_{\mathrm{mix}}^3\epsilon^{-2}\right)$, independent of $(1-\gamma)^{-1}$. Matching lower bounds establish the sharpness of these leading dependencies and reveal a separation between estimation and control: although the Q-function can be learned up to an additive constant at a horizon-free rate, policy learning generally retains its $(1-\gamma)^{-2}$ dependence.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2302.07477v4제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.