arXiv:1812.04363

Exploration Bonus for Regret Minimization in Undiscounted Discrete and Continuous Markov Decision Processes

Jian Qian, Ronan Fruit, Matteo Pirotta, Alessandro Lazaric

제출 2018-12-11

원문 초록

We introduce and analyse two algorithms for exploration-exploitation in discrete and continuous Markov Decision Processes (MDPs) based on exploration bonuses. SCAL$^+$ is a variant of SCAL (Fruit et al., 2018) that performs efficient exploration-exploitation in any unknown weakly-communicating MDP for which an upper bound C on the span of the optimal bias function is known. For an MDP with $S$ states, $A$ actions and $\Gamma \leq S$ possible next states, we prove that SCAL$^+$ achieves the same theoretical guarantees as SCAL (i.e., a high probability regret bound of $\widetilde{O}(C\sqrt{\Gamma SAT})$), with a much smaller computational complexity. Similarly, C-SCAL$^+$ exploits an exploration bonus to achieve sublinear regret in any undiscounted MDP with continuous state space. We show that C-SCAL$^+$ achieves the same regret bound as UCCRL (Ortner and Ryabko, 2012) while being the first implementable algorithm with regret guarantees in this setting. While optimistic algorithms such as UCRL, SCAL or UCCRL maintain a high-confidence set of plausible MDPs around the true unknown MDP, SCAL$^+$ and C-SCAL$^+$ leverage on an exploration bonus to directly plan on the empirically estimated MDP, thus being more computationally efficient.

함께 살펴볼 논문

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

arXiv:2410.01432v3cs.LG공통 태그 Efficient Exploration공식 코드 · Papers with Code

상각 샘플러를 위한 적응형 교사

Adaptive teachers for amortized samplers

상각 추론(Amortized inference)은 신경망과 같은 매개변수 모델을 학습시켜, 정확한 샘플링이 불가능한 주어진 비정규화 밀도(unnormalized density)의 분포를 근사하는 작업이다. 샘플링이 순차적 의사결정 과정으로 구현될 때, 생성 플로우 네트워크(generative flow networks)와 같은 강화학습(RL) 방법을 사용하여 샘플링 정책을 학습시킬 수 있다. 오프-정책 강화학습 학습은 다양하고 보상이 높은 후보를 발견하는 데 도움이 되지만, 기존 방법들은 효율적인 탐험에서 여전히 어려움을 겪는다. 우리는 적응형 학습 분포(\teacher)를 사용하여 주된 상각 샘플러(\student)의 학습을 안내할 것을 제안한다. 보조 행동 모델인 \teacher는 \student의 손실이 큰 영역에서 샘플링하도록 학습되며, 아직 탐험되지 않은 모드들로 일반화할 수 있어 효율적인 학습 커리큘럼을 제공함으로써 모드 커버리지(mode coverage)를 향상시킨다. 우리는 탐험 과제를 제시하도록 설계된 합성 환경, 두 가지 확산 기반 샘플링 과제, 그리고 네 가지 생화학적 발견 과제에서 이 접근법의 효과를 검증하며, 샘플 효율성과 모드 커버리지를 개선할 수 있음을 보인다. 소스 코드는 https://github.com/alstn12088/adaptive-teacher 에서 확인할 수 있다.

토론

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