Markov Decision Process (MDP)

The State Space is the set of all possible configurations of the environment. A state s ∈ S is a complete description that satisfies the Markov Property: the future is independent of the past given the present. In robotics, a state could be the robot's joint angles and object positions. States can be discrete (e.g., board positions in chess) or continuous (e.g., velocity and position).

The Action Space is the set of all possible moves or decisions the agent can make from a given state. An action a ∈ A(s) transitions the agent between states. Actions can be discrete (e.g., 'move left', 'grasp') or continuous (e.g., a torque vector). The design of the action space is critical; a poorly defined space can make learning intractable. Hierarchical actions, like the Options Framework, provide temporal abstraction.

The Transition Function, or dynamics model P(s' | s, a), defines the probability of transitioning to state s' after taking action a in state s. It encapsulates the environment's stochasticity. In Model-Based Reinforcement Learning (MBRL), the agent learns an approximation of this function. Ensemble Dynamics use multiple models to estimate uncertainty, which is crucial for robust planning and exploration.

The Reward Function R(s, a, s') provides a scalar feedback signal defining the agent's goal. It is the primary mechanism for specifying desired behavior. The agent's objective is to maximize the expected cumulative sum of discounted future rewards. Designing a reward function that aligns with complex goals is a major challenge (reward shaping). Intrinsic Motivation methods create internal rewards (e.g., for novelty) to drive exploration when external rewards are sparse.

The Discount Factor γ ∈ [0, 1] determines the present value of future rewards. A value of 1 makes the agent consider all future rewards equally (infinite horizon), while a value of 0 makes it myopic, caring only about the immediate reward. It ensures the infinite sum of rewards is finite and allows the agent to trade off short-term versus long-term gains. It is a hyperparameter that influences the optimal policy.

While not a formal component of the MDP tuple, the solution is defined by:

• Policy (π): A strategy mapping states to actions π(a|s). Can be deterministic or stochastic.
• State-Value Function V^π(s): The expected return starting from state s and following policy π.
• Action-Value Function Q^π(s, a): The expected return after taking action a in state s and thereafter following π. These functions are central to algorithms like Monte Carlo Tree Search (MCTS) and are used to evaluate and improve policies.

A Partially Observable Markov Decision Process (POMDP) extends the MDP framework for environments where the agent cannot directly perceive the true state. Instead, it receives only observations that are probabilistically related to the state. The agent must maintain a belief state—a probability distribution over possible true states—and its policy maps belief states to actions. This formalism is critical for robotics and real-world applications where sensors are noisy and information is incomplete.

• Core Challenge: Optimal decision-making under uncertainty.
• Key Component: The belief state, updated via Bayes' rule.
• Example: A robot navigating by camera must infer its precise location (state) from ambiguous visual inputs (observations).

Model-Based Reinforcement Learning (MBRL) is a paradigm where an agent explicitly learns a model of the environment's dynamics (transition function) and reward function. This learned world model can then be used for planning—simulating future trajectories to evaluate actions—without costly real-world interaction. MBRL aims for high sample efficiency.

• Contrast with Model-Free RL: Model-free methods (e.g., DQN, PPO) learn a policy or value function directly from experience without a dynamics model.
• Architectures: Include Recurrent State-Space Models (RSSM) for learning from pixels and algorithms like MuZero that learn implicit models for planning.
• Use Case: Training robot policies primarily in simulation before real-world deployment.

Monte Carlo Tree Search (MCTS) is a heuristic search algorithm for optimal decision-making in MDPs and other domains. It builds a search tree by performing simulated rollouts (playouts) from the current state. It balances exploration of less-visited actions with exploitation of promising ones using a formula like UCB1. MCTS is famously central to AlphaGo and AlphaZero.

• Four Steps: Selection, Expansion, Simulation, Backpropagation.
• Strengths: Anytime algorithm (improves with more computation), requires no explicit positional evaluation function.
• Integration with RL: Often used as a planning subroutine within a learned model, as in MuZero, or to provide improved policy targets for neural network training.

The options framework introduces temporal abstraction into reinforcement learning. An option is a temporally extended action, defined by a triple: an initiation set (states where it can start), an internal policy (mapping states to primitive actions), and a termination condition. This allows an agent to operate at a higher level, executing skills over multiple time steps.

• Purpose: Enables hierarchical reasoning, improves exploration, and accelerates learning in long-horizon tasks.
• Relation to MDPs: An MDP extended with options forms a Semi-Markov Decision Process (SMDP).
• Example: An option for "navigate to kitchen" encapsulates the low-level steps of avoiding obstacles and opening doors, terminating upon kitchen arrival.

Successor representations factor the classic value function of an MDP. Instead of representing the expected cumulative future reward from a state, they separate it into a successor matrix (expected future state occupancy) and an immediate reward vector. Formally, the value function V(s) = M(s, s') * r(s'), where M is the successor representation.

• Key Advantage: Fast adaptation to changes in reward. If rewards change, the agent can recompute optimal values instantly by re-multiplying M with the new r, without re-learning dynamics.
• Biological Plausibility: Thought to be a model of hippocampal place cell activity.
• Link to Transfer Learning: Encodes the dynamics of the environment independently of task-specific rewards.

A bisimulation metric defines a distance between states in an MDP based on behavioral equivalence. Two states are close if they lead to similar distributions over immediate rewards and next states, and this similarity propagates indefinitely into the future. It answers the question: "Which states are functionally the same for decision-making?"

• Contrast with Euclidean Distance: Raw sensory differences (e.g., pixel colors) may be large, but bisimulation distance could be zero if the states have identical downstream consequences.
• Application in State Representation: Used to learn bisimulation metrics that aggregate states, creating compact, task-relevant abstractions that improve generalization and sample efficiency in deep RL.
• Formal Basis: Grounded in the theory of Markov decision processes and probabilistic bisimulation.