벨만 잔차의 상하한 설정: 할인 보상 및 평균 보상 강화학습의 표본 복잡도 규명
Bellman Residual Bracketing: Resolving the Sample Complexity of Discounted and Average-Reward RL
한국어 초록
본 연구는 생성 모델을 사용할 수 있는 강화학습(RL)에서 경험적 계획법인 플러그인 접근의 표본 복잡도를 조사한다. 할인 플러그인 방법은 표본 $O(SA (1-\gamma)^{-3} \varepsilon^{-2} \log(SA/\delta))$개로 $\varepsilon$-최적 정책을 찾는다. 여기서 $S, A, \gamma, \delta$는 각각 상태 집합의 크기, 행동 집합의 크기, 할인 계수, 실패 확률이다. 평균 보상 설정에서는 할인 플러그인과 직접 플러그인(비할인 방식)의 표본 복잡도가 각각 $O(SAH\varepsilon^{-2}\log(SA/\delta))$와 $O(SAD\varepsilon^{-2}\log(SA/\delta))$임을 보인다. $H$는 최적 편향 함수의 범위에 대한 상한이고 $D$는 지름이다. 이 결과와 비적응 생성 모델의 하한을 결합하면, 할인 강화학습과 평균 보상 강화학습의 최소최대 표본 복잡도를 상수 배율 차이까지 규명한다. 평균 보상 설정에서는 편향 함수의 범위를 기준으로 한 계열과 지름을 기준으로 한 계열이 모두 해당한다. 주요 기술적 기여는 벨만 잔차를 상한과 하한으로 제한하는 새로운 기법이다. 이 기법은 흡수 상태가 있는 마르코프 의사결정 과정(MDP)에 기반한 기존 확률 집중 분석의 효율을 높인다.
원문 초록
We study the sample complexity of the empirical planning or plug-in approach for reinforcement learning (RL) with a generative model. We show the discounted plug-in approach finds an $\varepsilon$-optimal policy with $O(SA (1-\gamma)^{-3} \varepsilon^{-2} \log(SA/\delta))$ samples, where $S, A, \gamma, \delta$ are the state and action sizes, discount factor, and failure probability, respectively. In the average-reward setting, we show that discounted plug-in and direct (undiscounted) plug-in achieve $O(SAH\varepsilon^{-2}\log(SA/\delta))$ and $O(SAD\varepsilon^{-2}\log(SA/\delta))$ complexities, respectively, where $H$ upper-bounds the optimal bias span and $D$ is the diameter. Combining with our lower bounds for nonadaptive generative models, these results resolve the minimax sample complexity of discounted RL and average-reward RL --- in both the span- and diameter-based classes --- up to constant factors. Our main technical contribution is a novel Bellman residual bracketing technique which improves the efficiency of prior absorbing-MDP-based concentration analyses.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2611.19566v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
공통 태그로 연결된 공개 논문이 아직 없습니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.