Reinforcement Learning Theory: PAC Bounds and Planning

Module: Machine Learning | Difficulty: Advanced

PAC Bound for tabular MDPs

where = states, = actions, = discount.

Realizable vs Agnostic

• Realizable:
• Agnostic:

Planning Complexity

Model-Free vs Model-Based

import numpy as np

class ValueIteration:
    def __init__(self, P, R, gamma=0.99):
        self.P = P; self.R = R; self.gamma = gamma
        self.n_states, self.n_actions = P.shape[:2]
    def solve(self, theta=1e-8):
        V = np.zeros(self.n_states)
        while True:
            V_new = np.zeros(self.n_states)
            for s in range(self.n_states):
                q_values = np.zeros(self.n_actions)
                for a in range(self.n_actions):
                    q_values[a] = self.R[s,a] + self.gamma * self.P[s,a] @ V
                V_new[s] = q_values.max()
            if np.max(np.abs(V_new - V)) < theta:
                break
            V = V_new
        # Extract policy
        policy = np.zeros(self.n_states, dtype=int)
        for s in range(self.n_states):
            q_values = np.array([self.R[s,a] + self.gamma * self.P[s,a] @ V for a in range(self.n_actions)])
            policy[s] = q_values.argmax()
        return V, policy

Research Insight: The fundamental trade-off in RL is exploration vs exploitation. The sample complexity bound shows that the number of samples needed grows linearly with the number of states, making model-based methods more sample-efficient than model-free methods.