DescriptionEffectively leveraging model structure in reinforcement learning is a difficult task, but failure to do so can result in computer agents that repeatedly take sub-optimal actions, despite having enough information to perform better. The Bayesian approach is a principled and well-studied method for leveraging model structure, and it is useful to use in the reinforcement learning setting. This dissertation studies different methods for bringing the Bayesian approach to bear for model-based reinforcement learning agents, as well as different models that can be used. The contributions include several examples of models that can be used for learning MDPs, and two novel algorithms, and their analyses, for using those models for efficient exploration: BOSS and BFS3. The Bayesian approach to model-based reinforcement learning provides a principled method for incorporating prior knowledge into the design of an agent, and allows the designer to separate the problems of planning, learning and exploration. The BOSS and BFS3 algorithms are efficient (polynomial time) mechanisms for decision making within this framework with provable bounds on their accuracy.