Information-Theoretic Confidence Bounds for Reinforcement Learning
  We integrate information-theoretic concepts into the design and analysis of
optimistic algorithms and Thompson sampling. By making a connection between
information-theoretic quantities and confidence bounds, we obtain results that
relate the per-period performance of the agent with its information gain about
the environment, thus explicitly characterizing the exploration-exploitation
tradeoff. The resulting cumulative regret bound depends on the agent's
uncertainty over the environment and quantifies the value of prior information.
We show applicability of this approach to several environments, including
linear bandits, tabular MDPs, and factored MDPs. These examples demonstrate the
potential of a general information-theoretic approach for the design and
analysis of reinforcement learning algorithms.
