Self-accelerated Thompson sampling with near-optimal regret upper bound

Thompson sampling utilizes Bayesian heuristic strategy to balance the exploration-exploitation trade-off. It has been applied in a variety of practical domains and achieved great success. Despite being empirically efficient and powerful, Thompson sampling has eluded theoretical analysis. Existing analyses of Thompson sampling only provide regret upper bound of O˜(d3/2T) for linear contextual bandits, which is worse than the information-theoretic...