Dynamic Programming (DP) and Monte Carlo (MC) represent two foundational methods in reinforcement learning, each with distinct approaches but sharing the common goal of learning an optimal policy to maximize cumulative discounted rewards.
Dynamic Programming (DP)
Dynamic programming is a suite of algorithms that simplify complex problems by breaking them down into easier subproblems. In reinforcement learning, DP solves Bellman’s equations to find optimal policies without requiring agent-environment interaction. This method utilizes value functions to predict outcomes, necessitating complete knowledge of the environment’s dynamics—such as transition probabilities and reward functions—making it a model-based approach.
DP methods, including policy iteration and value iteration, employ bootstrapping, where value estimates are updated based on other value estimates. Consider a mouse in a gridworld with four states (C1 to C4), where C1 is a trap with a reward of -1, C4 contains cheese with a reward of +1, and C2 and C3 offer no rewards. Starting with all state values initialized to zero:
Values are updated using the Bellman equation.
For instance, when updating V(C2), we initially use V(C1) = 0 and V(C3) = 0.
Then when updating V(C3), we use new V(C2) and V(C1) = 0
Iteratively, values for each state are updated until convergence, demonstrating the bootstrapping process where estimates are refined using other estimates.
Monte Carlo (MC)
Monte Carlo methods enable learning directly from agent-environment interaction without a predefined model, classifying them as model-free approaches. Each episode—a complete sequence of states, actions, and rewards—serves as a sample from which the agent learns. This sampling process forms the core of MC's learning mechanism.
In MC, actual returns from episodes are used to update the value functions:
The update formula, Vk+1(st)=Vk(st)+α[Gt−Vk(st)], where Gt is the actual return, Vk(st) is the current value estimate, and α is the learning rate. This rate helps modulate how much new information influences the value estimates, balancing speed and stability of learning. Gt−Vk(st) is the error term that defines how far off the V function’s estimate is from actual return.
Using the same mouse gridworld example for MC:
If the mouse takes a left action in state C2, it calculates the return from that episode.
It then tries a right action from the same state in a new episode to compare returns.
The agent continually interacts with the environment, updating its policy based on the actual returns observed, rather than predictions.
Comparing DP and MC
While DP is computationally efficient and fast due to its reliance on a full model of the environment, MC offers potentially greater accuracy as it learns from actual experiences, though at the cost of potentially slower convergence and higher data requirements. Temporal Difference (TD) learning later emerged as a hybrid approach, integrating the strengths of both DP and MC.
תגובות