Balancing exploration and exploitation in sequential decision making

The Problem

Imagine you're in a casino with multiple slot machines (bandits), each with an unknown probability of payout. How do you maximize your total reward over time? You need to balance:

• Exploration: Trying different machines to learn their payouts
• Exploitation: Playing the machine you believe has the highest payout

Epsilon-Greedy

The simplest approach: with probability \(\epsilon\), explore randomly; otherwise, exploit the best known action.

• Simple to implement
• Explores uniformly, even among clearly suboptimal actions

Upper Confidence Bounds (UCB)

UCB measures potential by an upper confidence bound of the reward value \(\hat{U}_{t}(a)\), so that the true value is below with high probability:

\[ Q(a) \le \hat{Q}_{t}(a) + \hat{U}_{t}(a) \]

The UCB algorithm always selects the action that maximizes this upper confidence bound:

\[ a_{t}^{UCB} = \arg\max_{a \in A} \left( \hat{Q}_{t}(a) + \hat{U}_{t}(a) \right) \]

The confidence bound \(\hat{U}_{t}(a)\) typically decreases as we observe more samples of action \(a\), following the principle of "optimism in the face of uncertainty."

Thompson Sampling

A Bayesian approach that maintains a probability distribution over the expected reward of each action:

1. Sample a reward estimate from each action's posterior distribution
2. Select the action with the highest sampled value
3. Update the posterior based on the observed reward

Thompson Sampling often achieves near-optimal regret bounds while being simple to implement.

Regret

We measure performance by regret: the difference between the reward we would have obtained by always playing the optimal action and what we actually received:

\[ R_T = T \cdot \mu^* - \sum_{t=1}^{T} r_t \]

where \(\mu^*\) is the expected reward of the best action.

Reading: Program2Tutor by Tongmu Mu, Karan Goel, and Emma Brunskill

Problem: Determining topic relationships and statistical student learning modeling is a comlpex process. Prior Work: 1. Prerequisite or knowledge graph of the related matericl can be automatically constructed given an algorithmic representation of the underlying material. 2. How to automatically progress a student through a knowledge graph with minimal assumptions about a model of the underlying student learning process. Contribution: 1. Preliminary work on uniting the idea of automatically generating a knowledge graph and progressing a student while learning. 2. Novel approach for identifying the initial background knowledge of the learner. In this work, the authors unify the ideas of automatic curriculum generation from execution traces and automatic problem selection using reinforcement learning techniques. Specifically, they use multi-armed bandit algorithm for problem selection (ZPDES) as it is less reliant than other methods on the underlying student learning model which can be advantageous. Additionally, the authors build on prior work in probabilistically detecting the knowledge boundary of the student and present a novel approach to determine the initial knowledge state of the student within the curriculum. Automatic Curriculum Generation from Execution Traces Let \( n \) be any positive integer. We say that a trace \( T_{1}\) is at least as complex as trace \( T_{2} \) if every n-gram of trace \( T_{2} \) is also present in trace \( T_{1}\). Progressing Students Using Multi-Armed Bandits This algorithm at each timestep selects a problem from within the set of problem types on the boundary of the student's knowledge, or the ZPD, that it predicts will give the most most reward, which is measured in terms of student learning progress. On initialization, all problems start with an initial unnormalized weight \( w_{a} = w_{i}\). The weights are normalized to ensure a proper probability distribution: The weights of the problems \( w_{a}\) in the ZPD are normalized and denoted as \( w_{a}^{n} \) and with probability \( p_{a} = w_{a}^{n}(1 - \gamma) + \gamma \frac{1}{|ZPD|}\), where \( a \in ZPD\). Once a problem is selected, it is presented to the student and correctness of the student answer for the \( i^{th}\) time the problem is presented is recorded as \( C_{i}\). References B. Clement, D. Roy, P.-Y. Oudeyer, and M. Lopes. Multi-armed bandits for intelligent tutoring systems. JEDM-Journal of Educational Data Mining, 7(n), 2015.

Reinforcement Learning - Lecture 1 - Emma Brunskill

Learning to Make Good Sequential Decisions

Key aspects of reinforcement learning:

• Optimization: Finding policies that maximize expected reward
• Exploration: Balancing exploration vs exploitation
• Generalization: Transferring knowledge to new situations
• Delayed Consequences: Decisions have long-term ramifications

Challenges

When planning: Decisions involve reasoning about not just immediate benefit but also longer-term ramifications.

When learning: Temporal credit assignment is hard - what caused later high or low rewards?

Policy

A policy is a mapping from past experience to action.

Comparison with Other Paradigms

Supervised Learning: Typically making one decision instead of a sequence of decisions.

Imitation Learning: Learns from experience of others, assumes input demos of good policies. Imitation + RL seems promising.

Sequential Decision Making Under Uncertainty

Goal: Maximize the total expected future reward (the world is stochastic so the agent maximizes rewards in expectation).

The Markov Assumption

State \(s_t\) is Markov if and only if:

$$p(s_{t+1} | s_t, a_t) = p(s_{t+1} | h_{t}, a_{t})$$

The current state is a sufficient statistic of history.

Problem Variants

• Finite horizon vs. infinite horizon
• Stationary vs. non-stationary