무한 시계(Infinite-Horizon) 할인 의사결정 과정을 위한 톰슨 샘플링
Thompson Sampling for Infinite-Horizon Discounted Decision Processes
한국어 초록
본 논문은 보상과 전이가 알려지지 않은 매개변수에 의존하는, 보렐(Borel) 상태 및 행동 공간을 갖는 할인 무한 시계 마르코프 결정 과정(MDP)에서의 학습 프레임워크를 제시한다. 이러한 환경에서 샘플링 기반 적응형 학습 알고리즘을 분석하기 위해, 샘플링된 매개변수를 과정의 이력에 명시적으로 포함하는 정준 확률 공간(canonical probability space)을 도입한다. 성능 기준으로는 할인 MDP 후회(regret) 분석에서 사용되는 기간별 준최적성 격차(suboptimality gap)를 채택하고, 이를 매개변수화된 베이지안 설정에 맞게 특수화한다. 이 양은 현재 시점부터 이후의 미래 성능에서 남아 있는 손실을 나타내므로, 이를 잔여 후회(residual regret)라고 부른다. 우리는 기대 잔여 후회를 이용하여 할인 MDP 후회 분석을 적응 제어의 점근적 할인 최적성(asymptotic discount optimality) 및 강화학습의 시간차 오차(temporal-difference error) 관점과 연결한다. 이어서 할인 무한 시계 MDP에서의 톰슨 샘플링(TS)에 초점을 맞춘다. 유한 상태 및 행동 공간에 대한 기존 연구에서 사용된 가정을 보렐 설정으로 확장한 가정 하에서, TS의 기대 잔여 후회가 지수적으로 빠르게 0으로 수렴함을 보인다. 또한 관련 극한의 존재를 보장하는 완만한 조건 하에서, 표본 경로(sample-path) 잔여 후회가 거의 확실하게(almost surely) 0으로 수렴하며 TS가 완전 학습(complete learning)을 달성함을 보인다.
원문 초록
This paper develops a framework for learning in discounted infinite-horizon Markov decision processes (MDPs) with Borel state and action spaces, whose rewards and transitions depend on an unknown parameter.To analyze sampling-based adaptive learning algorithms in this setting, we introduce a canonical probability space that explicitly incorporates sampled parameters into the history of the process. As a performance criterion, we adopt the per-period suboptimality gap used in discounted-MDP regret analysis and specialize it to our parametrized Bayesian setting. Since this quantity captures the remaining loss in future performance from the current period onward, we refer to it as residual regret. We use the expected residual regret to connect discounted-MDP regret analysis with asymptotic discount optimality from adaptive control and the temporal-difference error perspective from reinforcement learning. We then focus on Thompson sampling (TS) in discounted infinite-horizon MDPs. Under assumptions that extend those used in prior work on finite state and action spaces to the Borel setting, we show that the expected residual regret for TS converges to zero exponentially fast. We further show that, under mild conditions ensuring the existence of the relevant limits, the ample-path residual regret converges to zero almost surely and TS achieves complete learning.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2405.08253v4제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
Representative Action Selection for Large Action-Space Meta-Bandits
Steering Generative Models with Experimental Data for Protein Fitness Optimization
Addressing Missing Data Issue for Diffusion-based Recommendation
Dynamic Assortment Selection and Pricing with Censored Preference Feedback
Bandit-Based Prompt Design Strategy Selection Improves Prompt Optimizers
Langevin Soft Actor-Critic: Efficient Exploration through Uncertainty-Driven Critic Learning
토론
이 논문과 연결된 포럼 글이 아직 없습니다.