Markov Decision Processes

These flashcards cover the fundamental concepts of Markov Decision Processes (MDPs), including states, transitions, rewards, discounting, and methods for solving them like Value Iteration.

A* Search

A search algorithm that orders nodes by the sum of path cost and goal proximity: $f(n) = g(n) + h(n)$.

State-based Models

Models that represent the world as states and transitions triggered by actions, used for tasks requiring forethought like chess or robotics.

Markov Decision Process (MDP)

A stochastic state-based model used for environments with randomness, defined by states, actions, a transition function, and a reward function.

Markov Property

The principle that given the present state, the future and the past are independent; action outcomes depend only on the current state.

Transition Function $T(s, a, s')$

Also called the model or dynamics, it defines the probability of reaching state $s'$ derived from taking action $a$ in state $s$, denoted as $P(s'|s, a)$.

Reward Function $R(s, a, s')$

The numerical value received when transitioning from one state to another; the agent's goal is to maximize the sum of these rewards.

Q-state

A chance node in an MDP search tree represented by the pair $(s, a)$, where the agent has committed to an action but the outcome state is not yet realized.

Optimal Policy $\pi^*$

A mapping $\pi^*: S \rightarrow A$ that specifies the best action to take for every state to maximize expected utility.

Discounting $\gamma$

A method where rewards decay exponentially (multiplied by $\gamma$ each step) to prioritize immediate rewards over future ones and ensure algorithm convergence.

Stationary Preferences

The assumption that if one reward sequence is preferred to another today, it will be preferred the same way tomorrow.

Finite Horizon

An approach to infinite utilities where episodes are terminated after a fixed number of steps $T$, resulting in non-stationary policies.

Value of a State $V^*(s)$

The maximum expected utility starting in state $s$ and acting optimally thereafter.

Value of a Q-state $Q^*(s, a)$

The expected utility starting having taken action $a$ from state $s$ and acting optimally thereafter.

Bellman Equations

The recursive definitions that characterize optimal values: $V^*(s) = \text{max}_a \times Q^*(s, a)$.

Time-Limited Values $V_k(s)$

The optimal value of a state $s$ under the condition that the process must end in exactly $k$ more time steps.

Value Iteration

An algorithm that computes optimal values by iteratively updating state values until convergence using the formula $V_{k+1}(s) = \text{max}_a \times \textstyle \bigcap_{s'} P(s'|s, a) [R(s, a, s') + \textstyle \bigcap V_k(s')]$.