Information-Theoretic Confidence Bounds for Reinforcement Learning
Xiuyuan Lu · Benjamin Van Roy

Tue Dec 10th 05:30 -- 07:30 PM @ East Exhibition Hall B + C #183

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.

Author Information

Xiuyuan Lu (Stanford University)
Benjamin Van Roy (Stanford University)

More from the Same Authors