An Information-Theoretic Perspective on Credit Assignment in Reinforcement Learning

How do we formalize the challenge of credit assignment in reinforcement\nlearning? Common intuition would draw attention to reward sparsity as a key\ncontributor to difficult credit assignment and traditional heuristics would\nlook to temporal recency for the solution, calling upon the classic eligibility\ntrace. We posit that it is not the sparsity of the reward itself that causes\ndifficulty in credit assignment, but rather the \\emph{information sparsity}. We\npropose to use information theory to define this notion, which we then use to\ncharacterize when credit assignment is an obstacle to efficient learning. With\nthis perspective, we outline several information-theoretic mechanisms for\nmeasuring credit under a fixed behavior policy, highlighting the potential of\ninformation theory as a key tool towards provably-efficient credit assignment.\n