CS188 - Introduction to Artificial Intelligence (Search, CSPs & MDPs) Flashcards

Question 1

A* Search Evaluation Function

Accepted Answer

A* selects nodes for expansion using $f(n) = g(n) + h(n)$, where $g(n)$ is the exact backward cost from the start state to node $n$, and $h(n)$ is the estimated forward cost from $n$ to the goal.

Question 2

Admissible Heuristic

Accepted Answer

A heuristic $h(n)$ is **admissible** if it never overestimates the true cost to reach the goal: $0 \le h(n) \le h^*(n)$ for all $n$. Admissibility guarantees optimality in **Tree Search**.

Question 3

Consistent (Monotone) Heuristic

Accepted Answer

A heuristic is **consistent** if for every node $n$ and action $a$ reaching successor $n'$, $h(n) \le c(n, a, n') + h(n')$. Consistency guarantees optimality in **Graph Search** and implies admissibility.

Question 4

Uniform Cost Search (UCS)

Accepted Answer

UCS expands the node with the lowest path cost $g(n)$. It is complete and optimal if edge costs satisfy $c \ge \epsilon > 0$. Its time and space complexity are $O(b^{1 + \lfloor C^* / \epsilon \rfloor})$.

Question 5

Minimax Algorithm

Accepted Answer

An optimal strategy for deterministic, two-player, zero-sum games. MAX maximizes utility while MIN minimizes it:
$V(s) = \max_{a \in A} V(	ext{Result}(s,a))$ for MAX nodes,
$V(s) = \min_{a \in A} V(	ext{Result}(s,a))$ for MIN nodes.

Question 6

Alpha-Beta Pruning Parameters

Accepted Answer

An optimization for Minimax that prunes redundant subtrees without altering the final decision:
- $\alpha$: Best (highest) value MAX can guarantee along the path.
- $\beta$: Best (lowest) value MIN can guarantee along the path.
Pruning occurs when $\alpha \ge \beta$.

Question 7

Evaluation Functions in Games

Accepted Answer

Functions used in depth-bounded Minimax to approximate state utilities at intermediate search depths when searching to terminal leaves is computationally infeasible.

Question 8

Constraint Satisfaction Problem (CSP) Formulation

Accepted Answer

A CSP is defined by a triple $(X, D, C)$:
- $X = \{X_1, \dots, X_n\}$: A set of variables.
- $D = \{D_1, \dots, D_n\}$: Domain of allowable values for each variable.
- $C = \{C_1, \dots, C_m\}$: Constraints restricting allowed assignments.

Question 9

Arc Consistency (AC-3 Algorithm)

Accepted Answer

An arc $X 	o Y$ is arc consistent if for every value $x \in D_X$, there is at least one value $y \in D_Y$ satisfying the constraint. AC-3 iteratively prunes values from domains until all arcs are consistent.

Question 10

MRV and LCV Heuristics

Accepted Answer

- **Minimum Remaining Values (MRV)**: Variable choice heuristic that selects the variable with the fewest legal values left ("fail-first").
- **Least Constraining Value (LCV)**: Value choice heuristic that picks the value ruling out the fewest choices in neighbor domains ("fail-last").

Question 11

Markov Decision Process (MDP) Formalism

Accepted Answer

A framework for modeling sequential decision-making under uncertainty, defined by $(S, A, T, R, \gamma)$:
- $S$: State space
- $A$: Action space
- $T(s,a,s') = P(s'|s,a)$: Transition model
- $R(s,a,s')$: Reward function
- $\gamma \in [0, 1)$: Discount factor

Question 12

Discount Factor ($\gamma$)

Accepted Answer

A scalar $\gamma \in [0, 1)$ reflecting preference for immediate rewards over future rewards. Cumulative utility is $U([r_0, r_1, \dots]) = \sum_{t=0}^{\infty} \gamma^t r_t$. It ensures mathematical convergence for infinite horizon problems.

Question 13

Bellman Optimality Equation for $V^*(s)$

Accepted Answer

Defines the value of state $s$ under an optimal policy:
$V^*(s) = \max_{a \in A} \sum_{s'} T(s,a,s') \left[ R(s,a,s') + \gamma V^*(s') \right]$

Question 14

Bellman Optimality Equation for $Q^*(s,a)$

Accepted Answer

Defines the expected utility of taking action $a$ in state $s$ and acting optimally thereafter:
$Q^*(s,a) = \sum_{s'} T(s,a,s') \left[ R(s,a,s') + \gamma \max_{a'} Q^*(s',a') \right]$
Note that $V^*(s) = \max_a Q^*(s,a)$.

Question 15

Value Iteration

Accepted Answer

A dynamic programming algorithm computing optimal values $V^*$ by repeatedly applying the update rule:
$V_{k+1}(s) \leftarrow \max_{a} \sum_{s'} T(s,a,s') \left[ R(s,a,s') + \gamma V_k(s') \right]$
Iterates until convergence: $\max_s |V_{k+1}(s) - V_k(s)| < \epsilon$.

Question 16

Policy Iteration Steps

Accepted Answer

Solves MDPs by alternating between two phases:
1. **Policy Evaluation**: Compute $V^{\pi_i}(s)$ for the current policy $\pi_i$.
2. **Policy Improvement**: Extract greedy policy $\pi_{i+1}(s) = \arg\max_a \sum_{s'} T(s,a,s') [R(s,a,s') + \gamma V^{\pi_i}(s')]$. Repeat until $\pi_{i+1} = \pi_i$.

Question 17

Model-Based vs. Model-Free Reinforcement Learning

Accepted Answer

- **Model-Based**: Learns transition estimates $T(s,a,s')$ and reward estimates $R(s,a,s')$ from samples, then solves for values using dynamic programming.
- **Model-Free**: Learns value estimates ($V$ or $Q$) directly from environment interactions without modeling $T$ or $R$.

Question 18

Q-Learning Update Rule

Accepted Answer

An off-policy model-free RL algorithm updated after transition sample $(s, a, r, s')$:
$Q(s,a) \leftarrow (1 - \alpha) Q(s,a) + \alpha \left[ r + \gamma \max_{a'} Q(s',a') \right]$
where $\alpha$ is the learning rate.

Question 19

Temporal Difference (TD) Error

Accepted Answer

The difference between the new sample estimate (target) and the previous value estimate:
$\delta = \left( r + \gamma \max_{a'} Q(s',a') \right) - Q(s,a)$
The Q-learning update simplifies to $Q(s,a) \leftarrow Q(s,a) + \alpha \delta$.

Question 20

Exploration vs. Exploitation ($\epsilon$-Greedy)

Accepted Answer

- **Exploration**: Taking actions to discover new transition/reward dynamics.
- **Exploitation**: Taking actions currently estimated to yield highest utility.
- **$\epsilon$-Greedy**: With probability $1 - \epsilon$, pick action $\arg\max_a Q(s,a)$; with probability $\epsilon$, pick a random uniform action.

CS188 - Introduction to Artificial Intelligence (Search, CSPs & MDPs)

Cards in this deck

Related Flashcard Sets

TypeScript - Advanced Type Systems, Generics & Design Patterns

Harvard ECON1011 - Intermediate Microeconomics: Game Theory & Market Structures

MIT 18.03 - Differential Equations: Ordinary Differential Equations, Laplace & Fourier

CPA Exam FAR - Financial Accounting & Reporting: US GAAP & Revenue Recognition