Statistics and Data Science Seminar Kevin Jamieson (University of Washington)
Instance Dependent PAC Bounds for Bandits and Reinforcement Learning
Abstract: The sample complexity of an interactive learning problem, such as multi-armed bandits or reinforcement learning, is the number of interactions with nature required to output an answer (e.g., a recommended arm or policy) that is approximately close to optimal with high probability. While minimax guarantees can be useful rules of thumb to gauge the difficulty…
