The Statistical Complexity of Interactive Decision Making VI: Posterior Sampling Bounds the Dual DEC of Tabular Reinforcement Learning by 26H²SA/γResearch Paper
In episodic reinforcement learning, an agent acts repeatedly in an unknown system and must learn which policy earns the largest expected reward. Even when states and actions are finite, the agent's choices change which data it observes. Foster, Kakade, Qian, and Rakhlin use the decision-estimation coefficient (DEC) to connect this information constraint to…