Modeling Exploration and Exploitation in Structured Environments
Abstract
In bandit problems, a decision-maker chooses repeatedly between a set of alternatives. They get feedback after every decision, either recording a reward or a failure. They also know that each alternative has some fixed unknown probability of providing a reward when it is chosen. The goal of the decision-maker is to obtain the maximum number of rewards over all the trials they complete. Bandit problems provide an interesting formal setting for studying the balance between exploration and exploitation in decision-making. In early trials, it makes sense to explore different alternatives, searching for those with the highest reward rates. In later trials, it makes sense to exploit those alternatives known to be good, by choosing them repeatedly. How exactly this balance between exploration and exploitation should be managed, and should be influenced by factors such as the distribution of reward rates, the total number of trials, and so on, raises basic questions about adaptation, planning, and learning in intelligent systems. This research project completed a series of inter-related lines of bandit problem research that improved our understanding of human and optimal sequential decision making using bandit problems.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 28, 2010
- Accession Number
- ADA567393
Entities
People
- Mark Steyvers
- Michael D Lee
Organizations
- University of California, Irvine