Reinforcement learning deals with general learning problems in which an 🧸 Agent seeks to achieve some goal in an environment formalized as a 🌎 Markov Decision Process (and in rare cases a 🎰 Multi-Armed Bandit or 📖 Contextual Bandit). This system can be broken down into four key components:

1. A policy defines how the agent behaves by defining what the agent should do in response to an observation from the environment.
2. A reward signal defines our goal for the agent by designating what states or actions are desirable. Our agent aims to maximize its expected total reward; that is, for some parameters that define our policy , our objective is to maximize

3. Value functions define the expected total reward. Thus, these functions define the long-term value of the state or state-action pair.
4. A model of the environment estimates how the environment behaves. This component is optional, but learning it allows our agent to perform planning.

Most RL algorithms share three key steps:

1. Generate samples: produce trajectories (of states, actions, and rewards), usually by running the policy in the environment.
2. Fit a model or estimate the return: compute something about the policy or environment (eg, dynamics or value).
3. Improve the policy: update the policy using the model.

However, the specifics of these steps are quite diverse, and algorithms differ in key tradeoffs: efficiency, stability, and prior assumptions. One key differentiator is whether the method models the environment dynamics—this divides algorithms into model-free and model-based.

Model-Free#

Model-free methods derive a policy directly from interacting with the environment without explicitly modeling the dynamics. Aside from the policy gradient, actor-critic, and value-based methods described below, 🐵 Imitation Learning is also model-free, though its problem setting and methods are different from most RL algorithms.

Policy Gradient#

🚓 Policy Gradients optimize the policy directly rather than using the value functions. These are most commonly with function approximation techniques since approximation ensures that similar states get similar actions. Some common policy gradients are below:

1. 🚑 Off-Policy Policy Gradient computes gradients using samples from another distribution (not the current policy).
2. 🚜 Natural Policy Gradient observes that the policy updates changes the future state-action data distribution and adds a distribution-change constraint to the gradient problem.
3. 🏦 Trust Region Policy Optimization improves the stability and efficiency of the natural policy gradient with conjugate gradient and line search for improvement.
4. 📪 Proximal Policy Optimization simplifies TRPO by incorporating the distribution constraint directly in a clipped objective.

Actor-Critic#

🎭 Actor-Critic methods estimate the state-value or action-value functions of a current policy in order to improve it.

1. 🎩 Off-Policy Actor-Critic modifies actor-critic to work with out-of-distribution samples from a replay buffer.
2. 🩰 A3C applies actor-critic updates asynchronously to stabilize training.
3. ⚔️ Deterministic Policy Gradients and 🧨 DDPG optimize a deterministic policy for Q-learning-like offline updates.
4. ✌️ TD3 improves DDPG training stability with more conservative value estimates.
5. 🪶 Soft Actor-Critic trains an offline actor-critic through 🎲 Entropy Regularization.

Value-Based#

Value-based methods estimate the state-value or action-value functions to derive a policy indirectly, without explicitly defining the policy.

1. 🪙 Monte Carlo Control is an approximation of dynamic programming using only samples from the environment.
2. ⌛️ Temporal Difference Learning combines dynamic programming and Monte Carlo control by learning from samples and bootstrapping updates. The most common instances of control are 🧭 Sarsa (on-policy) and 🚀 Q-Learning (off-policy).
3. 🪜 N-Step Bootstrapping bridges TD learning and Monte Carlo estimates by balancing the weight on samples versus bootstrap estimates.
4. 🎫 Eligibility Traces generalizes -step bootstrapping to average over all .

Model-Based#

Model-based methods use a model of the environment's dynamics, , to augment learning or decision-making. Generally, the dynamics can either be used to learn the value functions (background planning) or to make decisions during execution (decision-time planning).

Background Planning#

Background planning methods exploit the known probabilities to accurately estimate expectations over the environment.

1. 🧨 Dynamic Programming is a classic approach to estimating value functions using the environment dynamics and bootstrapping. The two most common implementations are ♻️ Policy Iteration and 💎 Value Iteration.
2. 🔮 Model Predictive Control and 💣 Dyna are methods that execute both model-learning and planning updates simultaneously.

Decision-Time Planning#

Decision-time planning supplements the policy by using the dynamics to choose an action when given state .

1. 🌲 Heuristic Search recursively checks the game tree and computes action-values using the dynamics probabilities.
2. 🎳 Rollout methods optimize a rollout policy that explores possible future trajectories and estimate action-values via sampling.
3. 🗺️ Monte Carlo Tree Search performs multiple rollouts directed toward trajectories that it estimates to have high value.