Reinforcement learning is a research field concerned with automatically solving problems by trial and error. With each trial, a reinforcement learning agent extracts information about the problem. The agent can choose to apply its current knowledge and solve the problem as well as that information allows, or it can decide to do something new and untried with the hope that this will yield new and useful information. Balancing this trade-off is called the exploration vs. exploitation problem, and is the primary focus of this thesis. The work is organized around three related research questions. Exploration algorithms have proliferated in the last few years. There are differences in the way exploration techniques create exploratory behavior. The first part of this work presents a categorization of exploration methods based on these differences. Techniques from each category are then tested and analyzed to evaluate their benefits and weaknesses. The categorization scheme makes it possible to easily combine exploration techniques. The second part of this work shows how to combine different exploration methods. Experimental results demonstrate that such a combination can produce new exploration algorithms which significantly outperform methods from each category. The best combined method outperforms the best single-category method, and is more robust to changes in the other parameters of the learning system. Combining methods from different categories of exploration techniques gives better results, but there are still some relatively simple problems the combined methods can not efficiently solve. The third part of the work further investigates the family of exploration techniques known as intrinsic motivation. Inspired by how humans are motivated to explore, the field of intrinsic motivation creates curious AI agents. The current state of the art intrinsic motivation techniques work very well on many problems but can not solve problems where the solution requires modeling randomness. This work investigates a novel intrinsic motivation algorithm designed to remove this known weakness.