Links

Abstract

optimism principle 에 기반한 알고리즘은 문제에 대한 구조를 exploit 하는데 실패하여 점근적으로 suboptimal 결과를 보임
context 분포와 exploration policy 가 나눠지도록 (decoupled) regret lower bound 를 reformulate 하여, unbalance 한 context distribution 에서도 robust 하게끔 알고리즘을 구성
그리고, incremental primal-dual 접근 방식을 사용하여 lower bound 의 Lagrangian relaxation 을 해결함 (solve)
최종적으로 강제적인 exploration 을 제거하고, 최소한의 exploration 을 encourage 하는 confidence intervals 을 build (for better adapting to the problem structure)
- 이를 asymptotic optimality 라고 부르고 있음