The Statistical Complexity of Interactive Decision Making I: Subadditivity of Squared Hellinger Distance for Sequential Laws, D²_H(P,Q) ≤ 10² log(n)·E_P[Σᵢ D²_H(P⁽ⁱ⁾, Q⁽ⁱ⁾)] for n ≥ 2Research Paper
Lower bounds for interactive decision making (bandits, reinforcement learning, and the general decision making with structured observations framework of Foster, Kakade, Qian and Rakhlin, arXiv:2112.13487) compare what a learner observes under two different environments. A learner's whole interaction history is generated one step at a time: each observation…