Bandit Algorithms for Tree Search
원문 초록
Bandit based methods for tree search have recently gained popularity when applied to huge trees, e.g. in the game of go [6]. Their efficient exploration of the tree enables to re- turn rapidly a good value, and improve preci- sion if more time is provided. The UCT algo- rithm [8], a tree search method based on Up- per Confidence Bounds (UCB) [2], is believed to adapt locally to the effective smoothness of the tree. However, we show that UCT is "over-optimistic" in some sense, leading to a worst-case regret that may be very poor. We propose alternative bandit algorithms for tree search. First, a modification of UCT us- ing a confidence sequence that scales expo- nentially in the horizon depth is analyzed. We then consider Flat-UCB performed on the leaves and provide a finite regret bound with high probability. Then, we introduce and analyze a Bandit Algorithm for Smooth Trees (BAST) which takes into account ac- tual smoothness of the rewards for perform- ing efficient "cuts" of sub-optimal branches with high confidence. Finally, we present an incremental tree expansion which applies when the full tree is too big (possibly in- finite) to be entirely represented and show that with high probability, only the optimal branches are indefinitely developed. We illus- trate these methods on a global optimization problem of a continuous function, given noisy values.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
입자 가속기 튜닝을 위한 분류기 가지치기 베이지안 최적화: 6차원 빔 위상 공간의 시간적 구조 매니폴드 탐험
Classifier-pruned Bayesian optimization for particle accelerator tuning: Exploring temporally structured manifold of 6D beam phase space
입자 가속기와 같은 복잡한 동역학 시스템은 최적 성능을 달성하기 위해 복잡하고 시간이 많이 소요되는 튜닝 절차를 종종 필요로 한다. 많은 경우 이러한 절차는 시공간 빔의 동역학을 지배하는 최적 시스템 매개변수를 추정해야 하므로, 이 작업은 고차원 최적화 문제가 된다. 이를 해결하기 위해, 우리는 6차원 빔 위상 공간의 시간적 구조 잠재 매니폴드 내에서 효율적인 탐험을 위한 프레임워크인 Classifier-pruned Bayesian Optimization-based Latent space Tuner(CBOL-Tuner)를 제안한다. CBOL-Tuner는 잠재 공간 표현을 위한 조건부 변분 오토인코더(conditional variational autoencoder), 시간적 동역학을 위한 장단기 메모리(long short-term memory) 신경망, 매개변수 추정을 위한 경량 신경망, 그리고 최적해를 위한 잠재 공간을 적응적으로 탐색하고 필터링하는 분류기 가지치기 베이지안 옵티마이저를 통합한다.
상각 샘플러를 위한 적응형 교사
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 에서 확인할 수 있다.
NeRF-based CBCT Reconstruction needs Normalization and Initialization
A Hybrid GA LLM Framework for Structured Task Optimization
MermaidFlow: Redefining Agentic Workflow Generation via Safety-Constrained Evolutionary Programming
A Divide-and-Conquer Approach for Global Orientation of Non-Watertight Scene-Level Point Clouds Using 0-1 Integer Optimization
토론
이 논문과 연결된 포럼 글이 아직 없습니다.