the setup

1. initial state: $s_0$
2. actions at each state: go( $s_1$), go( $s_2$)
3. transition model: result( $s_0$, go( $s_1$)) = $s_1$
4. goal states: $s_\text{goal}$
5. path cost function: cost( $s_0$, a, $s_1$)

how to search

• TREE-SEARCH - continuously expand the frontier
  • frontier = set of all leaf nodes available to expand
• GRAPH-SEARCH - also keep set of visited states

metrics

• optimal - finds best solution
• complete - terminates in finite steps
• time, space complexity
  • search cost - just time/memory
• total cost - search cost + path cost

summary

informed search

• informed search - use $g(n)$ and $h(n)$
  • g(n): cost from start to n
  • heuristic h(n): cost from n to goal
• best-first - choose nodes with best f
  • f=g: uniform-cost search
  • f=h: greedy best-first search
• $A^*$: $f(n) = g(n) + h(n)$

admissible

• admissible: $h(n)$ never overestimates
• $\implies A^*$ (with tree search) is optimal and complete

consistent

• consistent: $h(n) \leq cost(n \to n') + h(n')$
  • monotonic
• $\implies A^*$ (with graph search) is optimal and complete

optimally efficient

• consistent $\implies$ optimally efficient (guaranteed to expand fewest nodes)
  • never re-open a node
• weaknesses
  • must store all nodes in memory

memory-bounded heuristic search

• iterative-deepening $A^*$ - cutoff f-cost
• recursive best-first search
  • each selected node backs up best f alternative
  • if exceeding this, rewind
  • when rewinding, replace nodes with with best child f
• $SMA^*$ - simplified memory-bounded
  • when memory full, collapse worst leaf

recursive best-first

heuristic functions

• want big h(n) because we expand everything with $f(n) < C^*$

  • $h_1$ dominates $h_2$ if $h_1(n) \geq h_2(n) \: \forall \: n$
  • combining heuristics: pick $h(n) = max[h_1(n), ..., h_m(n)]$

• relaxed problem yields admissible heuristics

  • ex. 8-tile solver

definitions

• local search looks for solution not path ~ like optimization
• maintains only current node and its neighbors

discrete space

• hill-climbing = greedy local search
  • stochastic hill climbing
  • random-restart hill climbing
• simulated annealing - pick random move
  • if better accept
  • else accept with probability $\exp(\Delta f / T_t)$
• local beam search - pick k starts, then choose the best k states from their neighbors
  • stochastic beam search - pick best k with prob proportional to how good they are

genetic algorithms

schema - representation

continuous space

• could just discretize neighborhood of each state

• SGD: line search - double $\alpha$ until f increases

• Newton-Raphson method: $x = x - H_f^{-1} (x) \nabla f(x)$

definitions

• variables, domains, constraints
• goal: assignment of variables
  • consistent - doesn't violate constraints
  • complete - every variable is assigned
• 2 ways to solve
  1. local search - assign all variables and then alter
  2. backtracking search (with inference) - assign one at a time

example

1 - local search for csps

• start with some assignment to variables
• min-conflicts heuristic - change variable to minimize conflicts
  • can escape plateaus with tabu search - keep small list of visited states
  • could use constraint weighting

2 - backtracking

• depth-first search that backtracks when no legal values left
  • b1 - variable and value ordering
  • b2 - interleaving search and inference
  • b3 - intelligent backtracking - looking backward

b1 - variable and value ordering

• commutative
• heuristics
  • minimum-remaining-values
  • degree - pick variable involved in most constraints
  • least-constraining-value

b2 - interleaving search and inference

• forward checking - after assigning, check arc-consistency on neighbors
• maintaining arc consistency (MAC) - after assigning, arc consistency initialized on neighbors

constraint graph

this is not the search graph!

inference

• constraint propagation uses constraints to prune domains of variables
• finite-domain constraint $\equiv$ set of binary constraints w/ auxiliary variables
  • ex. dual graph transformation: constraint $\to$ variable, shared variables $\to$ edges

basic constraint propagation

• node consistency - unary constraints
• arc consistency - satisfy binary constraints (AC-3 algorithm)
  • for each arc, apply it
    • if things changed, re-add all the neighboring arcs to the set
  • $O(cd^3)$ where $d = \vert domain\vert$, c = num arcs

advanced constraint propagation

• path consistency - consider constraints on triplets - PC-2 algorithm
  • extends to k-consistency
  • strongly k-consistent - also (k-1), ..., 1-consistent
    • $\implies O(k^2d)$ to solve
• global constraints

b3 - intelligent backtracking

• conflict set for each node (list of variable assignments that deleted things from its domain)
• backjumping - backtracks to most recent assignment in conflict set
• conflict-directed backjumping
  • let $X_j$ be current variable and $conf(X_j)$ be conflict set. If every possible value for $X_j$ fails, backjump to the most recent variable $X_i$ in $conf(X_j)$ and set $conf(X_i) = conf(X_i) \cup conf(X_j) - X_i$
• constraint learning - finding min set of assigments from conflict set that causes problem

structure of problems

• connected components of constraint graph are independent subproblems
• tree - any 2 variables are connected by only one path
  • directed arc consistency - ordered variables $X_i$, every $X_i$ is consistent with each $X_j$ for j>i
    • tree with n nodes can be made directed arc-consisten in $O(n)$ steps - $O(nd^2)$

making trees

1. assign variables so remaining variables form a tree
   • assigned variables called cycle cutset with size c
   • $O[d^c \cdot (n-c) d^2]$
   • finding smallest cutset is hard, but can use approximation called cutset conditioning
2. tree decomposition - view each subproblem as a mega-variable
   • tree width w - size of largest subproblem - 1
   • solvable in $O(n d^{w+1})$

what are game trees?

• adversarial search problems - adversaries attempt to keep us from goal state

components

• states have utilities ~ like the score obtained at a state
• state's value is often best possible utility obtainable from a state

minimax algorithm

• visit nodes in postorder traversal (like DFS)
• at each decision node, pick the node with best utility

alpha-beta pruning

• can stop searching a branch if we know it won't be picked

evaluation functions

• estimate utility of a node
• often do this as a linear function of features

nondeterministic search

• multiple successors can result from an action (w/ some prob)
• can represent this as a a game tree with expectimax chance nodes
• mdps can help solve these problems
• goal: find a policy $\pi$ which maps states to actions

elements

• standard: states, actions, start, terminal states
• transition function: $T(s, a, s')$
• reward function: $R(s, a, s')$
• try to maximize sum of rewards or discounted sum of rewards

mdps

• memoryless: $T(s, a, s') = P(s'|s, a)$
• value $V^*(s)$ = maximum expected utility starting at s
• q-value $Q^*(s, a)$ = maximum expected utility starting in s, taking action a

the bellman eqn

• $V^(s) = \underset{a}{\max}\: Q^(s, a)$
  • $Q^(s, a) = \underset{s'}{\sum} T(s, a, s')[R(s, a, s') + \gamma V^(s')]$
• condition for optimality

value iteration

initialize state values to zero and iteratively them

1. $V_0(s) = 0$

2. Bellman update for each state

3. once we have values for each state, $\pi^(s) = \underset{a}{\text{argmax}} \: Q^(s, a)$

policy iteration

initialize policy and iteratively update it

1. define $\pi_0(s)$
2. Bellman update for policy, where values are computed using the current policy $V^\pi_i(s)$

what is rl

• don't know rewards / transitions, but want to learn best policy to optimize rewards
• must balance exploration with exploitation
• uses samples or episodes = samples until reaching a terminal state

types of rl

• model-based learn transition + rewards and used value/policy iteration vs model-free: directly estimate values /q-values
  • keeping counts of transitions can be memory-intensive
• passive (given policy - e.g. direct evaluation, TD-learning) and active (e.g. Q-learning) needs to learn policy
• on-policy learning requires policy to be optimal to learn optimal values while off-policy learning can learn optimal values following suboptimal policy (e.g. Q-learning)

equations

• direct methods: just keep track of counts
• TD (bellman eqn w/ fixed policy): $V^\pi(s) = \underset{s'}{\sum} T(s, \pi(s), s')\underbrace{ [R(s, \pi(s), s') + \gamma V^\pi (s')]}_{\text{sample}}$
  • exponential moving average: $V^\pi(s) = (1- \alpha) V^\pi (s) + \alpha \cdot sample$
• $Q{k+1}(s, a) = \underset{s'}{\sum} T(s, a, s') \cdot \underbrace{[R(s, a, s') + \gamma \underset{a'}{\max} Q(s', a')]}{\text{sample}}$ (like value iteration, but no max)
  • exponential moving average: $Q(s, a) = (1 - \alpha) Q(s, a) + \alpha \cdot sample$
  • approximate q-learning = use feature-based repr.

exploration + exploitation

• $\epsilon$-greedy policy - act randomly with probability $\epsilon$
• exploration function - replace Q(s, a) with some function based on how many times state has been visited

variables

1. query variables - unkown and we want to know them
2. evidence variables - known
3. hidden variables - present, but unknown

representation

• each node is conditionally indep of all ancestors given all of its parents
• d-separation - color evidence vars, they separate unles they are at a common effect (or downstream)

triples

	Causal chain	Common cause	Common effect
$X \perp Z$?	❌	❌	✅
$X \perp Z \vert Y$?	✅	✅	❌

inference

• inference by enumeration: sum over all the variables
• elimination: join all factors and sum them out
  • two steps: alternate joining and eliminating
  • want to pick ordering to create smallest factors

sampling

• prior sampling: sample and throw away things which don't match
• rejection sampling: throw away anything as soon as it doesn't match
• likelihood weighting - fix evidence variables and weight them by their likelihood
• gibbs sampling - set variables random and repeatedly resample one var at a time

what is a decision network?

similar to bayes nets, but we add 2 things:

1. action nodes - we have complete control
2. utility nodes - give us a result

decision theory

• $EU(a|e) = \sum_{s'} P(s'|s, a) U(s')$
• $MEU(e) = \underset{a}{\max} EU(a|e)$
• $VPI(T) = E_T[MEU(e, t)] - MEU(e)$