Extended Formulations for Online Linear Bandit Optimization
원문 초록
On-line linear optimization on combinatorial action sets (d-dimensional actions) with bandit feedback, is known to have complexity in the order of the dimension of the problem. The exponential weighted strategy achieves the best known regret bound that is of the order of $d^{2}\sqrt{n}$ (where $d$ is the dimension of the problem, $n$ is the time horizon). However, such strategies are provably suboptimal or computationally inefficient. The complexity is attributed to the combinatorial structure of the action set and the dearth of efficient exploration strategies of the set. Mirror descent with entropic regularization function comes close to solving this problem by enforcing a meticulous projection of weights with an inherent boundary condition. Entropic regularization in mirror descent is the only known way of achieving a logarithmic dependence on the dimension. Here, we argue otherwise and recover the original intuition of exponential weighting by borrowing a technique from discrete optimization and approximation algorithms called `extended formulation'. Such formulations appeal to the underlying geometry of the set with a guaranteed logarithmic dependence on the dimension underpinned by an information theoretic entropic analysis.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
상각 샘플러를 위한 적응형 교사
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 에서 확인할 수 있다.
MermaidFlow: Redefining Agentic Workflow Generation via Safety-Constrained Evolutionary Programming
DISCOVER: Automated Curricula for Sparse-Reward Reinforcement Learning
ForesightNav: Learning Scene Imagination for Efficient Exploration
Disentangling Uncertainties by Learning Compressed Data Representation
Reward-Centered ReST-MCTS: A Robust Decision-Making Framework for Robotic Manipulation in High Uncertainty Environments
토론
이 논문과 연결된 포럼 글이 아직 없습니다.