Model a search problem

• Defining a search problem

  • $s_{\text{start}}$: stating state.
  • Actions$\left(s\right)$: possible actions
  • Cost$(s,a)$: action cost
  • Succ$(s,a)$: the successor state
  • IsEnd$\left(s\right)$: reached end state?

• A search tree

  • Node: a state
  • Edge: an (action, cost) pair
  • Root: starting state
  • Leaf nodes: end states

• Each root-to-leaf path represents a possible action sequence, and the sum of the costs of the edges is the cost of that path

• Objective: find a minimal cost path to the end state

• Coding a search problem: a class with the following methods:

  • stateState() -> State
  • isEnd(State) -> bool
  • succAndCost(State) -> List[Tuple[str, State, float]] returns a list of (action, state, cost) tuples.

Tree search algorithms

• $b$: actions per state, $D$ maximum depth, $d$ depth of the solution path

• Always exponential time
• Avoid exponential spaces with DFS-ID

Uniform cost search (UCS)

Figure source: Stanford CS221 spring 2025, lecture slides week 3

• Types of states

  • Explored: optimal path found; will not update cost to these states in the future
  • Frontier: states we’ve seen, but still can update the cost of how to get there cheaper (i.e., priority queue)
  • Unexplored: states we haven’t seen

• Uniform cost search (UCS) algorithm

  • Add $s_{\text{start}}$ to frontier
  • Repeat until fronteir is empty:
    • Remove $s$ with smallest priority (minimum cost to $s$ among visited paths) $p$ from frontier
    • If $\text{IsEnd}\left(s\right)$: return solution
    • Add $s$ to explored
    • For each action $a\in \text{Actions(s)}$:
      • Get successor $s^{\prime }\leftarrow \text{Succ}(s,a)$
      • If $s^{\prime }$ is already in explored: continue
      • Update frontier with $s^{\prime }$ and priority with $p+\text{Cost}(s,a)$ (if it’s cheaper)

• Properties of UCS

  • Correctness: When a state $s$ is popped from the frontier and moved to explored, its priority is PastCost$\left(s\right)$, the minimum cost to $s$.

  • USC potentially explores fewer states, but requires move overhead to maintain the priority queue

A*

• A* algorithm: Run UCS with modified edge costs $${\text{Cost}}^{\prime }(s,a)=\text{Cost}(s,a)+h\left(\text{Succ}\right(s,a\left)\right)-h\left(s\right)$$

  • USC: explore states in order of PastCost$\left(s\right)$
  • A*: explore states in order of PastCost$\left(s\right)+h\left(s\right)$
  • $h\left(s\right)$ is a heuristic that estimates FutureCost$\left(s\right)$

• Heuristic $h$

  • Consistency:

    • Triangle inequality: ${\text{Cost}}^{\prime }(s,a)=\text{Cost}(s,a)+h\left(\text{Succ}\right(s,a\left)\right)-h\left(s\right)\ge 0$, and
    • $h\left(s_{\text{end}}\right)=0$

    

    Figure source: Stanford CS221 spring 2025, lecture slides week 3

  • Admissibility: $$h\left(s\right)\le \text{FutureCost}\left(s\right)$$

  • If $h\left(s\right)$ is consistent, then it is admissible.

• A* properties

  • Correctness: if $h$ is consistent, then A* returns the minimum cost path
  • Efficiency: A* explores all states $s$ satisfying $$\text{PastCost}\left(s\right)\le \text{PastCost}\left(s_{\text{end}}\right)-h\left(s\right)$$
    • If $h\left(s\right)=0$, then A* is the same as UCS
    • If $h\left(s\right)=\text{FutureCost}\left(s\right)$, then A* only explores nodes on a minimum cost path
    • Usually somewhere in between

• Create $h\left(s\right)$ via relaxation

  • Remove constraints
  • Reduce edge costs (from $\infty$ to some finite cost)

Model an MDP

• Markove decision process definition:
  • States: the set of states
  • $s_{\text{start}}$: stating state.
  • Actions$\left(s\right)$: possible actions
  • $T(s,a,s^{\prime })$: transition probability of $s^{\prime }$ if take action $a$ in state $s$
  • Reward$(s,a,s^{\prime })$: reward for the transition $(s,a,s^{\prime })$
  • IsEnd$\left(s\right)$: reached end state?
  • $\gamma \in (0,1]$: discount factor
• A policy $\pi$: a mapping from each state $s\in \text{States}$ to an action $a\in \text{Actions}\left(s\right)$

Policy Evaluation (on-policy)

• Utility of a policy is the discounted sum of the rewards on the path

  • Since the policy yields a random path, its utility is a random variable

• For a policy, its path is $s_0,a_1{r}_1{s}_1,a_2{r}_2{s}_2,\dots$ (action, reward, new state) tuple, then the utility with discount $\gamma$ is $$u_1=r_1+\gamma r_2+{\gamma }^2{r}_3+\dots$$

• $V_{\pi }\left(s\right)$: the expected utility (called value) of a policy $\pi$ from state $s$

• $Q_{\pi }(s,a)$: Q-value, the expected utility of taking action $a$ from state $s$, and then following policy $\pi$

• Connections between $V_{\pi }\left(s\right)$ and $Q_{\pi }(s,a)$:

$$V_{\pi }\left(s\right)=\{\begin{array}{cc}0& \text{if IsEnd}\left(s\right)\\ Q_{\pi }(s,\pi (s\left)\right)& \text{otherwise}\end{array}$$

$$Q_{\pi }(s,a)=\sum _{s^{\prime }}T(s,a,s^{\prime })\left[\text{Reward}\right(s,a,s^{\prime })+\gamma V_{\pi }(s^{\prime }\left)\right]$$

• Iterative algorithm for policy evaluation

  • Initialize $V_{\pi }^{\left(0\right)}\left(s\right)=0$ for all $s$
  • For iteration $t=1,\dots ,t_{\text{PE}}$:
    • For each state $s$, $$V_{\pi }^{\left(t\right)}\left(s\right)=\sum _{s^{\prime }}T(s,\pi (s),s^{\prime })[\text{Reward}(s,\pi (s),s^{\prime })+\gamma V_{\pi }^{(t-1)}(s^{\prime }\left)\right]$$

• Choice of $t_{\text{PE}}$: stop when values don’t change much $$\underset{s}{max}\left|V_{\pi }^{\left(t\right)}\right(s)-V_{\pi }^{(t-1)}(s\left)\right|\le ϵ$$

• MDP time complexity is $O\left(t_{\text{PE}}S{S}^{\prime }\right)$, where $S$ is the number of states and $S^{\prime }$ is the number of $s^{\prime }$ with $T(s,a,s^{\prime })\ge 0$

Value Iteration (off-policy)

• Optimal value $V_{\text{opt}}\left(s\right)$: maximum value attained by any policy

• Optimal Q-value $Q_{\text{opt}}(s,a)$

$$Q_{\text{opt}}(s,a)=\sum _{s^{\prime }}T(s,a,s^{\prime })\left[\text{Reward}\right(s,a,s^{\prime })+\gamma V_{opt}(s^{\prime }\left)\right]$$

$$V_{\text{opt}}\left(s\right)=\{\begin{array}{cc}0& \text{if IsEnd}\left(s\right)\\ {max}_{a\in \text{Actions}\left(s\right)}{Q}_{\text{opt}}(s,a)& \text{otherwise}\end{array}$$

• Value iteration algorithm:
  • Initialize $V_{\text{opt}}^{\left(0\right)}\left(s\right)=0$ for all $s$
  • For iteration $t=1,\dots ,t_{\text{VI}}$:
    • For each state $s$, $$V_{\text{opt}}^{\left(t\right)}\left(s\right)=\underset{a\in \text{Actions}\left(s\right)}{max}\sum _{s^{\prime }}T(s,a,s^{\prime })[\text{Reward}(s,a,s^{\prime })+\gamma V_{\text{opt}}^{(t-1)}(s\left)\right]$$
• VI time complexity is $O\left(t_{\text{VI}}SA{S}^{\prime }\right)$, where $S$ is the number of states, $A$ is the number of actions, and $S^{\prime }$ is the number of $s^{\prime }$ with $T(s,a,s^{\prime })\ge 0$

Model-based methods (off-policy)

$${\hat{Q}}_{\text{opt}}(s,a)=\sum _{s^{\prime }}\hat{T}(s,a,s^{\prime })\left[\widehat{\text{Reward}}\right(s,a,s^{\prime })+\gamma {\hat{V}}_{opt}(s^{\prime }\left)\right]$$

• Based on data $s_0;a_1,r_1,s_1;a_2,r_2,s_2;\dots ;a_n,r_n,s_n$, estimate the transition probabilities and rewards of the MDP

$$\begin{array}{cc}\hat{T}(s,a,s^{\prime })& =\frac{\#\text{times}(s,a,s^{\prime })\text{occurs}}{\#\text{times}(s,a)\text{occurs}}\\ \widehat{\text{Reward}}(s,a,s^{\prime })& =r\text{in}(s,a,r,s^{\prime })\end{array}$$

• If $\pi$ is a non-deterministic policy which allows us to explore each (state, action) pair infinitely often, then the estimates of the transitions and rewards will converge.
  • Thus, the estimates $\hat{T}$ and $\widehat{\text{Reward}}$ are not necessarily policy dependent. So model-based methods are off-policy estimations.

Model-free Monte Carlo (on-policy)

• The main idea is to estimate the Q-values directly

• Original formula $${\hat{Q}}_{\pi }(s,a)=\text{average of}{u}_t\text{where}{s}_{t-1}=s,a_t=a$$

• Equivalent formulation: for each $(s,a,u)$, let $$\begin{array}{cc}\eta & =\frac{1}{1+\#\text{updates to}(s,a)}\\ {\hat{Q}}_{\pi }(s,a)& \leftarrow (1-\eta )\underset{\text{prediction}}{\underset{}{{\hat{Q}}_{\pi }(s,a)}}+\eta \underset{\text{data}}{\underset{}{u}}\\ & ={\hat{Q}}_{\pi }(s,a)-\eta \left({\hat{Q}}_{\pi }\right(s,a)-u)\end{array}$$

  • Implied objective: least squares $${\left({\hat{Q}}_{\pi }\right(s,a)-u)}^2$$

SARSA (on-policy)

• SARSA algorithm

On each $(s,a,r,s^{\prime },a^{\prime })$: $${\hat{Q}}_{\pi }(s,a)\leftarrow (1-\eta ){\hat{Q}}_{\pi }(s,a)+\eta [\underset{\text{data}}{\underset{}{r}}+\gamma \underset{\text{estimate}}{\underset{}{{\hat{Q}}_{\pi }(s^{\prime },a^{\prime })}}]$$

• SARSA uses estimates ${\hat{Q}}_{\pi }(s^{\prime },a^{\prime })$ instead of just raw data $u$

Q-learning (off-policy)

On each $(s,a,r,s^{\prime })$: $$\begin{array}{cc}{\hat{Q}}_{\text{opt}}(s,a)& \leftarrow (1-\eta )\underset{\text{prediction}}{\underset{}{{\hat{Q}}_{\text{opt}}(s,a)}}+\eta \underset{\text{target}}{\underset{}{[r+\gamma {\hat{V}}_{\text{opt}}(s^{\prime }\left)\right]}}\\ {\hat{V}}_{\text{opt}}\left(s^{\prime }\right)& =\underset{a^{\prime }\in \text{Actions}\left(s^{\prime }\right)}{max}{\hat{Q}}_{\text{opt}}(s^{\prime },a^{\prime })\end{array}$$

Epsilon-greedy

• Reinforcement learning algorithm template

  • For $t=1,2,3,\dots$
    • Choose action $a_t={\pi }_{\text{act}}\left(s_{t-1}\right)$
    • Receive reward $r_t$ and observe new state $s_t$
    • Update parameters

• What exploration policy ${\pi }_{\text{act}}$ to use? Need to balance exploration and exploitation.

• Epsilon-greedy policy $${\pi }_{\text{act}}\left(s\right)=\{\begin{array}{cc}\arg {max}_{a\in \text{Actions}\left(s\right)}{\hat{Q}}_{\text{opt}}(s,a)& \text{probability}1-ϵ\\ \text{random from Actions}\left(s\right)& \text{probability}ϵ\end{array}$$

Function appxomation

• Large state spaces is hard to explore.For better generalization to handle unseen states/actions, we can use function approximation, to define
  • features $\varphi (s,a)$, and
  • weights $w$, such that $${\hat{Q}}_{\text{opt}}(s,a;w)=w\cdot \varphi (s,a)$$
• Q-learning with function approximation: on each $(s,a,r,s^{\prime })$,

$$w\leftarrow w-\eta [\underset{\text{prediction}}{\underset{}{{\hat{Q}}_{\text{opt}}(s,a;w)}}-\underset{\text{target}}{\underset{}{(r+\gamma {\hat{V}}_{\text{opt}}(s^{\prime }\left)\right)}}]\varphi (s,a)$$

Game evaluation

• Use recurrence for policy evaluation to estimate value of the game (expected utility):

$$V_{\text{eval}}\left(s\right)=\{\begin{array}{cc}\text{Utility}\left(s\right)& \text{IsEnd}\left(s\right)\\ {\sum }_{a\in \text{Actions}\left(s\right)}{\pi }_{\text{agent}}(s,a)V_{\text{eval}}\left(\text{Succ}\right(s,a\left)\right)& \text{Player}\left(s\right)=\text{agent}\\ {\sum }_{a\in \text{Actions}\left(s\right)}{\pi }_{\text{opp}}(s,a)V_{\text{eval}}\left(\text{Succ}\right(s,a\left)\right)& \text{Player}\left(s\right)=\text{opp}\end{array}$$

Expectimax

• Expectimax: given opponent’s policy, find the best policy for the agent

$$V_{\text{exptmax}}\left(s\right)=\{\begin{array}{cc}\text{Utility}\left(s\right)& \text{IsEnd}\left(s\right)\\ {max}_{a\in \text{Actions}\left(s\right)}{V}_{\text{exptmax}}\left(\text{Succ}\right(s,a\left)\right)& \text{Player}\left(s\right)=\text{agent}\\ {\sum }_{a\in \text{Actions}\left(s\right)}{\pi }_{\text{opp}}(s,a)V_{\text{exptmax}}\left(\text{Succ}\right(s,a\left)\right)& \text{Player}\left(s\right)=\text{opp}\end{array}$$

Minimax

• Minimax assumes the worst case for the opponent’s policy

$$V_{\text{minmax}}\left(s\right)=\{\begin{array}{cc}\text{Utility}\left(s\right)& \text{IsEnd}\left(s\right)\\ {max}_{a\in \text{Actions}\left(s\right)}{V}_{\text{minmax}}\left(\text{Succ}\right(s,a\left)\right)& \text{Player}\left(s\right)=\text{agent}\\ {min}_{a\in \text{Actions}\left(s\right)}{V}_{\text{minmax}}\left(\text{Succ}\right(s,a\left)\right)& \text{Player}\left(s\right)=\text{opp}\end{array}$$

Figure source: Stanford CS221 spring 2025, lecture slides week 5

• Minimax properties

  • Best against minimax opponent $$V({\pi }_{max},{\pi }_{min})\ge V({\pi }_{\text{agent}},{\pi }_{min})\text{for all}{\pi }_{\text{agent}}$$
  • Lower bound against any opponent $$V({\pi }_{max},{\pi }_{min})\le V({\pi }_{max},{\pi }_{\text{opp}})\text{for all}{\pi }_{\text{opp}}$$
  • Not optimal if opponent is known! Here, ${\pi }_7$ stands for an arbitrary known policy, for example, random choice with equal probabilities. $$V({\pi }_{max},{\pi }_7)\ge V({\pi }_{\text{exptmax}\left(7\right)},{\pi }_7)\text{for opponent}{\pi }_7$$

• Relationship between game values

Figure source: Stanford CS221 spring 2025, lecture slides week 5

Expectiminimax

• Modify the game to introduce randomness

Figure source: Stanford CS221 spring 2025, lecture slides week 5

• This is equivalent to having a third player, the coin $$V_{\text{exptminmax}}\left(s\right)=\{\begin{array}{cc}\text{Utility}\left(s\right)& \text{IsEnd}\left(s\right)\\ {max}_{a\in \text{Actions}\left(s\right)}{V}_{\text{exptminmax}}\left(\text{Succ}\right(s,a\left)\right)& \text{Player}\left(s\right)=\text{agent}\\ {min}_{a\in \text{Actions}\left(s\right)}{V}_{\text{exptminmax}}\left(\text{Succ}\right(s,a\left)\right)& \text{Player}\left(s\right)=\text{opp}\\ {\sum }_{a\in \text{Actions}\left(s\right)}{\pi }_{\text{coin}}(s,a)V_{\text{exptminmax}}\left(\text{Succ}\right(s,a\left)\right)& \text{Player}\left(s\right)=\text{coin}\end{array}$$

Evaluation functions

• Computation complexity: with branching factor $b$ and depth $d$ (number of turns $2d$ because of two players), since this is a tree search, we have

  • $O\left(d\right)$ space
  • $O\left(b^{2d}\right)$ time

• Limited depth tree search: stop at maximum depth $d_{max}$ $$V_{\text{minmax}}(s,d)=\{\begin{array}{cc}\text{Utility}\left(s\right)& \text{IsEnd}\left(s\right)\\ \text{Eval}\left(s\right)& d=0\\ {max}_{a\in \text{Actions}\left(s\right)}{V}_{\text{minmax}}\left(\text{Succ}\right(s,a),d)& \text{Player}\left(s\right)=\text{agent}\\ {min}_{a\in \text{Actions}\left(s\right)}{V}_{\text{minmax}}\left(\text{Succ}\right(s,a),d-1)& \text{Player}\left(s\right)=\text{opp}\end{array}$$

  • Use: at state $s$, call $V_{\text{minmax}}(s,d_{max})$

• An evaluation function Eval$\left(s\right)$ is a possibly very weak estimate of the value $V_{\text{minmax}}\left(s\right)$, using domain knowledge

  • This is similar to FutureCost$\left(s\right)$ in the A* search problems. But unlike A*, there are no guarantees on the error for approximation.

Alpha-Beta pruning

• Branch and bound

  • Maintain lower and upper bounds on values.
  • If intervals don’t overlap, then we can choose optimally without future work

• Alpha-beta prining for minimax:

  • $a_s$: lower bound on value of max node $s$
  • $b_s$: upper bound on value of min node $s$
  • Store ${\alpha }_s={max}_{s^{\prime }\le s}{a}_{s^{\prime }}$ and ${\beta }_s={min}_{s^{\prime }\le s}{b}_{s^{\prime }}$
  • Prune a node if its interval doesn’t have non-trivial overlap with every ancestor

• Pruning depends on the order

  • Worse ordering: $O\left(b^{2\cdot d}\right)$ time
  • Best ordering: $O\left(b^{2\cdot 0.5d}\right)$ time
  • Random ordering: $O\left(b^{2\cdot 0.75d}\right)$ time, when $b=2$
  • In practice, we can order based on the evaluation function Eval$\left(s\right)$:
    • Max nodes: order successors by decreasing Eval$\left(s\right)$
    • Min nodes: order successors by increasing Eval$\left(s\right)$

TD learning (on-policy)

• General learning framework

  • Objective function $$\frac{1}{2}{\left(\text{prediction}\right(w)-\text{target})}^2$$
  • Update $$w\leftarrow w-\eta \left(\text{prediction}\right(w)-\text{target}){\nabla }_w\text{prediction}\left(w\right)$$

• Temporal difference (TD) learning: on each $(s,a,r,s^{\prime })$,

  $$w\leftarrow w-\eta \left[V\right(s;w)-(r+\gamma V(s^{\prime };w\left)\right)]{\nabla }_{w}V(s;w)$$

  • For linear function $$V(s;w)=w\cdot \varphi \left(s\right)$$

Simultaneous games

• Payoff matrix: for two players, $V(a,b)$ is A’s utility if A chooses action $a$ and B chooses action $b$

• Strategies (policies)

  • Pure strategy: a single action
  • Mixed strategy: a probability distribution of actions

• Game evaluation: the value of the game if player A follows ${\pi }_A$ and player B follows ${\pi }_B$ is $$V({\pi }_A,{\pi }_B)=\sum _{a,b}{\pi }_A\left(a\right){\pi }_B\left(b\right)V(a,b)$$

• For pure strategies, going second is no worse $$\underset{a}{max}\underset{b}{min}V(a,b)\le \underset{b}{min}\underset{a}{max}V(a,b)$$

• Mixed strategy: second play can play pure strategy: for any fixed mixed strategy ${\pi }_A$, ${min}_{{\pi }_B}V({\pi }_A,{\pi }_B)$ can be obtained by a pure strategy

• Minimax theorem: for every simultaneous two-player zero-sum game with a finite number of actions $$\underset{{\pi }_A}{max}\underset{{\pi }_B}{min}V({\pi }_A,{\pi }_B)=\underset{{\pi }_B}{min}\underset{{\pi }_A}{max}V({\pi }_A,{\pi }_B)$$

  • Revealing your optimal mixed strategy doesn’t hurt you.