Eluder Dimension and Sample Complexity of Optimistic Exploration
Xuhui Liu (NJU)
Short abstract: In MAB and RL setting, eluder dimension is a notion that measures the function complexity like VC dimension in supervised learning. Eluder dimension does this by measuring the degree of dependence among action rewards. We will use this notion to analyze sample complexity of MAB using Thompson sampling methods.
Reference: Russo D , Roy B V . Eluder Dimension and the Sample Complexity of Optimistic Exploration[J]. Advances in Neural Information Processing Systems, 2013:2256-2264.