Midterm Summary

Agents and environments

• an agent perceives its environment through sensors and acts upon it through actuators (or effectors, depending on whom you ask)
• the agent function maps percept sequences to actions
• it is generated by an agent program running on a machine

   Agent                              Environment
     |  <-- Sensors  <-- Percepts <--     |
     |  --> Actuators --> Actions -->     |

The task environment: PEAS

• Performance Measure
• -1 per step
• +10 food
• +500 win
• -500 die
• +200 hit scared ghost
• Environment
• Pacman dynamics (incl. ghost behavior)
• Actuators
• Left / Right / Up / Down, or NSEW
• Sensors
• entire state is visible (except power pellet duration)

Agent design

The environment type largely determines the agent design: - partially observable → agent requires memory (internal state) - stochastic → agent may have to prepare for contingencies - multi-agent → agent may need to behave randomly - static → agent has time to compute a rational decision - continuous time → continuously operating controller - unknown physics → need to explore in reinforcement learning - unknown perf. measure → observe/interact with human principal

Utilities and Rationality

mapping state of the world to a real value

Utility: map state of world to real value

rational preferences — the five axioms: - Orderability: \((A > B) \lor (B > A) \lor (A \sim B)\) - Transitivity: \((A > B) \land (B > C) \Rightarrow (A > C)\) - Continuity: \((A > B > C) \Rightarrow \exists p\ [p, A;\ 1-p, C] \sim B\) - Substitutability: \((A \sim B) \Rightarrow [p, A;\ 1-p, C] \sim [p, B;\ 1-p, C]\) - Monotonicity: \((A > B) \Rightarrow \big( (p \geq q) \Leftrightarrow [p, A;\ 1-p, B] \geq [q, A;\ 1-q, B] \big)\)

given rational preferences, there exists \(U(X)\) s.t. - \(U(A) \geq U(B) \Leftrightarrow A \geq B\) - \(U([p_1, S_1;\ \dots;\ p_n, S_n]) = p_1 U(S_1) + \dots + p_n U(S_n)\)

MAXIMIZE UR EXPECTED UTILITY

Search Problems

the first part was search problems - a search problem consists of a state space - a successor function (with actions, costs) - a start state and a goal test

A solution is a sequence of actions (a plan) that transforms the start state to a goal state

State space Graphs vs Search Trees

• each node in a search tree is an entire path in the state space graph
• we construct only what we need on demand

state space graph              search tree
  (finite, cycles OK)            (can be infinite; each node = a path)

      S                                  S
     / \                               /   \
    a   b                            a      b
     \ /                            / \    / \
      c                            c   c  c   c
                                   |   |  |   |
                                  ... ... ... ...

General Tree search

• important ideas
• fringe
• expansion
• expansion strategy
• main question: which fringe nodes to explore?

def tree_search(problem, fringe):
    fringe.push(make_node(problem.start_state))
    while True:
        if fringe.is_empty(): return failure
        node = fringe.pop()
        if problem.goal_test(node.state): return node.path
        for child in expand(node, problem):
            fringe.push(child)

DFS

• expand the deepest node first
• We use a LIFO stack to go as deep as possible
• Storage is really good, but Time complexity is really bad
• If \(m\) is finite, it takes time \(O(b^m)\)
• largest space is the largest path — fringe only holds siblings on the path to root, so \(O(bm)\)
• complete? \(m\) could be infinite, so only if we prevent cycles
• optimal? No — it finds the "leftmost" solution, regardless of depth or cost

BFS

• expand the shallowest node first
• implementation: fringe is a FIFO queue
• processes all nodes above the shallowest solution; let that depth be \(s\)
• time \(O(b^s)\); space \(O(b^s)\) (roughly the last tier)
• complete? yes — \(s\) must be finite if a solution exists
• optimal? only if all costs are 1

UCS

• orders by path cost, cheapest node first
• fringe is a priority queue keyed on cumulative cost \(g(n)\)
• time and space \(O(b^{C^*/\varepsilon})\) where \(C^*\) is the optimal cost and \(\varepsilon\) the minimum arc cost
• complete and optimal (assuming positive costs)
• BFS finds the shortest path in terms of number of actions; it does not find the least-cost path — UCS does

Greedy

• orders by proximity — expand the node that seems closest, i.e. smallest heuristic value \(h(n)\)
• a heuristic estimates how close a state is to a goal, designed for a particular search problem (e.g. Manhattan distance, Euclidean distance)
• optimal? No — the resulting path to Bucharest is not the shortest

A*

• combines both: UCS orders by backward cost \(g(n)\), greedy orders by forward cost \(h(n)\)
• A* orders by the sum \(f(n) = g(n) + h(n)\)

when should A* terminate? - only when we remove the goal - we want to take the path only when we dequeue a goal node, because there can be a better path added before we dequeue it

\(h\) is admissible iff \(0 \leq h(n) \leq h^*(n)\) for all \(n\), where \(h^*(n)\) is the true cost to a nearest goal - i.e. the heuristic never overestimates — it's optimistic - often, admissible heuristics are solutions to relaxed problems, where new actions are available - coming up with admissible heuristics is most of what's involved in using A* in practice - inadmissible heuristics are often useful too

Graph Search

for any given search problem

how do we decide our fringe, how do we explore, etc.

def graph_search(problem, fringe):
    closed = set()                      # states already expanded
    fringe.push(make_node(problem.start_state))
    while True:
        if fringe.is_empty(): return failure
        node = fringe.pop()
        if problem.goal_test(node.state): return node.path
        if node.state not in closed:
            closed.add(node.state)
            for child in expand(node, problem):
                fringe.push(child)

the main idea here is admissibility

consistency - main idea: estimated heuristic costs \(\leq\) actual costs - admissibility: heuristic cost \(\leq\) actual cost to goal — \(h(v) \leq h^*(v)\) for all \(v \in V\). underestimate the true cost to the goal! - consistency: heuristic "arc" cost \(\leq\) actual cost for each arc — \(h(u) - h(v) \leq d(u, v)\) for all \((u, v) \in E\). underestimate the weight of every edge! - consequences of consistency: - the \(f\) value along a path never decreases: \(h(A) \leq \text{cost}(A \to C) + h(C)\) - A* graph search is optimal

if it's admissible, it's optimal (tree A); with a consistent heuristic, graph A is optimal

the same proof shows UCS is optimal where \(h = 0\) (trivial)

CONSTRAINT SATISFACTION

• coloring australia

• \(N\) variables, domain \(D\), constraints

• States, Goal Tests, Successor Function

• states: partial assignment
• goal test: complete assignment that satisfies all constraints
• successor function: assign an unassigned variable

Backtracking Search

• backtracking search is the basic uninformed algorithm for solving CSPs
• assign one variable at a time
• variable assignments are commutative so fix ordering = better branching factor
• i.e. [WA = red then NT = green] is the same as [NT = green then WA = red]
• need to consider assignments to a single variable at each step
• Check constraints as you go
• i.e. consider only values which do not conflict with previous assignments
• might have to do some computation to check the constraints
• "incremental goal test"
• depth-first search with these two improvements is called backtracking search (not the best name)
• can solve \(n\)-queens for \(n \approx 25\)
• backtracking = DFS + variable-ordering + fail-on-violation

backtracking example - every single step we check the constraints, fail on violation

def backtracking_search(csp):
    return recursive_backtracking({}, csp)

def recursive_backtracking(assignment, csp):
    if assignment is complete: return assignment
    var = select_unassigned_variable(csp, assignment)     # MRV
    for value in order_domain_values(var, assignment, csp):   # LCV
        if value is consistent with assignment:
            assignment[var] = value
            inferences = inference(csp, var, value)       # forward checking / AC-3
            if inferences != failure:
                result = recursive_backtracking(assignment, csp)
                if result != failure: return result
            remove var and inferences from assignment
    return failure

Filtering: Forward Checking

• keep track of the domains for unassigned variables and cross off bad options
• forward checking: cross off values that violate a constraint when added to the existing assignment
• as a result of doing the first assignment we cross off some values
• forward checking propagates information from assigned to unassigned variables, but doesn't provide early detection for all failures (e.g. NT and SA cannot both be blue — why didn't we detect this yet?)
• Constraint Propagation: reason from constraint to constraint

Arc Consistency

• an arc \(X \to Y\) is consistent iff for every \(x\) in the tail there is some \(y\) in the head which could be assigned without violating a constraint
• delete from the tail!
• forward checking = enforcing consistency of arcs pointing to each new assignment
• if I modify a domain, I need to check all of its children as well, add them to the queue of arcs, and then we expand them

def AC_3(csp):
    queue = all arcs (Xi, Xj) in csp
    while queue is not empty:
        (Xi, Xj) = queue.pop()
        if remove_inconsistent_values(Xi, Xj):
            if domain(Xi) is empty: return failure
            for Xk in neighbors(Xi) - {Xj}:
                queue.push((Xk, Xi))
    return success

def remove_inconsistent_values(Xi, Xj):
    removed = False
    for x in domain(Xi):
        if no y in domain(Xj) satisfies the constraint (x, y):
            delete x from domain(Xi)
            removed = True
    return removed

\(O(n^2 d^3)\) why? - there are at most \(n^2\) arcs (each ordered pair of the \(n\) variables) - each arc can be pushed back onto the queue at most \(d\) times, since it only gets re-added when a value is deleted from its head's domain, and a domain has \(d\) values → at most \(n^2 d\) arc revisions - each call to remove_inconsistent_values costs \(O(d^2)\): for each of the \(d\) values in the tail, scan all \(d\) values in the head - total: \(n^2 d \cdot d^2 = O(n^2 d^3)\) - can be reduced to \(O(n^2 d^2)\) by caching, for each tail value, a supporting head value so you don't rescan from scratch - ... but detecting all possible future problems is NP-hard

K-Consistency

increasing degrees of consistency: - 1-consistency (node consistency): each single node's domain has a value which meets that node's unary constraints - 2-consistency (arc consistency): for each pair of nodes, any consistent assignment to one can be extended to the other - k-consistency: for each \(k\) nodes, any consistent assignment to \(k-1\) can be extended to the \(k\)th node - higher \(k\) is more expensive to compute - (you need to know the \(k = 2\) case: arc consistency)

We then talked about other ideas of expansion

MRV

choose one with the least remaining values left in the domain - fail fast ordering - also called "most constrained variable"

LCV

choose the least constraining value, one that rules out the fewest values in the remaining variables - note that it may take some computation to determine this (e.g. rerunning filtering) - combining these ordering ideas makes 1000 queens feasible

Iterative algorithms for CSPs

local search methods typically work with "complete" states, i.e. all variables assigned

to apply to CSPs: - take an assignment with unsatisfied constraints - operators reassign variable values - no fringe! live on the edge

def min_conflicts(csp, max_steps):
    current = a complete random assignment for csp
    for i in range(max_steps):
        if current satisfies all constraints: return current
        var = a randomly chosen conflicted variable
        value = the value for var that minimizes total violated constraints
        current[var] = value
    return failure

• variable selection: randomly select any conflicted variable
• value selection: min-conflicts heuristic — choose a value that violates the fewest constraints, i.e. hill climb with \(h(x)\) = total number of violated constraints

Tree structured CSPs

• choose a root variable; order variables so that parents precede children
• remove backward: for \(i = n : 2\), apply RemoveInconsistent(Parent(Xi), Xi)
• assign forward: for \(i = 1 : n\), assign \(X_i\) consistently with Parent(Xi)
• runtime: \(O(n d^2)\) — \(n-1\) arcs, each revised once at \(O(d^2)\), with no re-queuing because the tree structure means backward passes never invalidate an earlier arc

Game playing: incorporate search with other agents

• different types of assumptions about agents. Need the best possible strategy.
• assume agents are in a competitive mode (zero sum) and they are effectively minimizing my output while maximizing theirs

The value of a state can be the best outcome from a state

Terminal States: \(V(s)\) known

Minimax

• states under the agent's control → MAX nodes: \(V(s) = \max_{s' \in \text{successors}(s)} V(s')\)
• states under the opponent's control → MIN nodes: \(V(s) = \min_{s' \in \text{successors}(s)} V(s')\)
• terminal states: \(V(s) = \text{utility}(s)\)

def value(state):
    if the state is terminal: return the state's utility
    if the next agent is MAX:  return max_value(state)
    if the next agent is MIN:  return min_value(state)

def max_value(state):
    v = -∞
    for successor in successors(state):
        v = max(v, value(successor))
    return v

def min_value(state):
    v = +∞
    for successor in successors(state):
        v = min(v, value(successor))
    return v

                    ▲ 3                 MAX picks the largest child
                /   |   \
             ▼      ▼      ▼            MIN picks the smallest child
            /|\    /|\    /|\
          3 12 8  2 4 6  14 5 2         terminal utilities

• time \(O(b^m)\), space \(O(bm)\) — same as exhaustive DFS

Alpha - Beta pruning

• \(\alpha\): MAX's best option on path to root
• \(\beta\): MIN's best option on path to root

def max_value(state, α, β):
    v = -∞
    for successor in successors(state):
        v = max(v, value(successor, α, β))
        if v >= β: return v
        α = max(α, v)
    return v

def min_value(state, α, β):
    v = +∞
    for successor in successors(state):
        v = min(v, value(successor, α, β))
        if v <= α: return v
        β = min(β, v)
    return v

• pruning has no effect on the minimax value of the root
• with a perfect ordering, time drops to \(O(b^{m/2})\) — doubles the solvable depth

Multi agent utilities

• what if the game is not zero-sum? or has multiple players?

generalization of minimax - terminals have utility tuples - node values are also utility tuples - each player maximizes its own component - can give rise to cooperation and competition dynamically

Chance nodes

• we don't know what the result of an action will be:
• explicit randomness: rolling dice
• unpredictable opponents
• actions can fail
• values should reflect average case (expectimax) outcomes, not worst-case (minimax) outcomes
• expectimax search: compute the average score under optimal play
• max nodes as in minimax search
• chance nodes: calculate expected utilities, \(V(s) = \sum_{s'} P(s' | s) V(s')\)

def value(state):
    if the state is a terminal state: return the state's utility
    if the next agent is MAX: return max_value(state)
    if the next agent is EXP: return exp_value(state)

def max_value(state):
    v = -∞
    for successor in successors(state):
        v = max(v, value(successor))
    return v

def exp_value(state):
    v = 0
    for successor in successors(state):
        p = probability(successor)
        v += p * value(successor)
    return v

MDPs

an MDP is defined by: - a set of states \(s \in S\) - a set of actions \(a \in A\) - a transition function \(T(s, a, s')\) - probability that \(a\) from \(s\) leads to \(s'\): \(P(s'|s, a)\) - also called the model or the dynamics - a reward function \(R(s, a, s')\) (sometimes just \(R(s)\) or \(R(s')\)) - a start state - maybe a terminal state

MDPs are non-deterministic search problems - one way to solve is with expectimax

Policies

• in deterministic search: we wanted a plan, a sequence of actions from start to goal
• for MDPs we want an optimal policy \(\pi^*: S \to A\)
• a policy gives an action for each state
• an optimal policy is one that maximizes expected utility if followed
• an explicit policy defines a reflex agent
• we want a way to define this policy
• expectimax didn't compute entire policies — it computed the action for a single state only

What is Markov about MDPs?

• given the present state, the future and past are independent
• action outcomes depend only on the current state
• for Markov Decision Processes:
• \(P(s_{t+1} = s' \mid s_t = s_t, a_t = a_t, s_{t-1}, a_{t-1}, \dots, s_0) = P(s_{t+1} = s' \mid s_t = s_t, a_t = a_t)\)
• this is just like search, where the successor function could only depend on the current state (not the history)

Discounting

In all of my configurations, I want to get the highest possible utility of reward - we use discounting; it's also reasonable to prefer rewards now to rewards later - one solution: values of rewards decay exponentially — worth \(1\) now, \(\gamma\) next step, \(\gamma^2\) in two steps - \(U([r_0, r_1, r_2, \dots]) = \sum_{t=0}^{\infty} \gamma^t r_t\)

the goal is to maximize the expected sum of discounted rewards

Optimal quantities

now we can have some quantities, by which we can get the max reward

• First \(V^*(s)\) is the expected utility starting in \(s\) and acting optimally
• the utility of a Q-state: \(Q^*(s, a)\) is the expected utility starting out having taken an action \(a\) from state \(s\) and thereafter acting optimally
• the optimal policy: \(\pi^*(s)\) = optimal action from state \(s\)

we have multiple \(Q(s, a)\) at every state, for each action that can be taken

VALUE ITERATION

computing the value or the q value function

start at \(V_0(s) = 0\) for each state — no time steps left means an expected reward sum of zero — and then we will compute the values

compute one step of expectimax for each state:

\(V_{k+1}(s) \leftarrow \max_a \sum_{s'} T(s, a, s')\big[R(s, a, s') + \gamma V_k(s')\big]\)

repeat till convergence

complexity of each iteration \(O(S^2 A)\)

def value_iteration(mdp, gamma, epsilon):
    V = {s: 0 for s in mdp.states}
    while True:
        V_new = {}
        for s in mdp.states:
            best = -∞
            for a in mdp.actions(s):
                q = 0
                for s_prime in mdp.states:
                    t = mdp.T(s, a, s_prime)
                    q += t * (mdp.R(s, a, s_prime) + gamma * V[s_prime])
                best = max(best, q)
            V_new[s] = best
        if max over s of abs(V_new[s] - V[s]) < epsilon: return V_new
        V = V_new

• theorem: will converge to unique optimal values
• basic idea: approximations get refined towards optimal values
• policy may converge long before values do
• value iteration is just a fixed point solution method, though the \(V_k\) vectors are also interpretable as time-limited values

the bellman equations

How to be optimal 1. take the correct first action 2. continue being optimal

• definition of optimal utility via expectimax recurrence gives a simple one-step lookahead relationship amongst optimal utility values
• \(V^*(s) = \max_a Q^*(s, a)\)
• \(Q^*(s, a) = \sum_{s'} T(s, a, s')\big[R(s, a, s') + \gamma V^*(s')\big]\)
• \(\pi^*(s) = \arg\max_a Q^*(s, a)\)
• combined: \(V^*(s) = \max_a \sum_{s'} T(s, a, s')\big[R(s, a, s') + \gamma V^*(s')\big]\)

these are the Bellman equations, and they characterize optimal values in a way we'll use over and over

POLICY EVALUATION

• how do we calculate the \(V\)'s for a fixed policy \(\pi\)?
• Idea 1: turn recursive bellman equations into updates (like value iteration)

\(V^\pi_0(s) = 0\)

\(V^\pi_{k+1}(s) = \sum_{s'} T(s, \pi(s), s')\big[R(s, \pi(s), s') + \gamma V^\pi_k(s')\big]\)

• efficiency: \(O(S^2)\) per iteration (no max over actions)
• Idea 2: without the maxes, the Bellman equations are just a linear system — solve with your favorite linear system solver

def policy_evaluation(mdp, policy, gamma, epsilon):
    V = {s: 0 for s in mdp.states}
    while True:
        V_new = {}
        for s in mdp.states:
            a = policy[s]
            total = 0
            for s_prime in mdp.states:
                t = mdp.T(s, a, s_prime)
                total += t * (mdp.R(s, a, s_prime) + gamma * V[s_prime])
            V_new[s] = total
        if max over s of abs(V_new[s] - V[s]) < epsilon: return V_new
        V = V_new

Computing actions from values

how do I compute my policy given an optimal value function

how should we act? it's pretty obvious, pick the action with the largest \(V\) for that action - from values it's not obvious — we need to do a mini-expectimax (one step): - \(\pi^*(s) = \arg\max_a \sum_{s'} T(s, a, s')\big[R(s, a, s') + \gamma V^*(s')\big]\) - this is called policy extraction, since it gets the policy implied by the values - from q-values it's completely trivial: - \(\pi^*(s) = \arg\max_a Q^*(s, a)\) - important lesson: actions are easier to extract from q-values than values!

POLICY ITERATION

• policy evaluation: calculate utilities for some fixed policy (not optimal utilities!) until convergence
• policy improvement: update policy using one step look-ahead with resulting (converged but not optimal) utilities as future values
• repeat until the policy stops changing

def policy_iteration(mdp, gamma):
    policy = {s: an arbitrary action for s in mdp.states}
    while True:
        V = policy_evaluation(mdp, policy, gamma, epsilon)
        stable = True
        for s in mdp.states:
            best_a, best_q = None, -∞
            for a in mdp.actions(s):
                q = 0
                for s_prime in mdp.states:
                    t = mdp.T(s, a, s_prime)
                    q += t * (mdp.R(s, a, s_prime) + gamma * V[s_prime])
                if q > best_q:
                    best_q, best_a = q, a
            if best_a != policy[s]:
                policy[s] = best_a
                stable = False
        if stable: return policy, V

this is policy iteration - it's still optimal and can converge much faster under some conditions

Reinforcement learning

• in MDPs we were given everything: \(T\), \(R\), etc.
• in Reinforcement learning, we don't know \(T\) and \(R\)
• still assume an MDP (\(S\), \(A\), \(T(s,a,s')\), \(R(s,a,s')\)), still looking for a policy \(\pi(s)\)

• new twist: we don't know which rewards are good or what the actions do, so we must actually try out actions and states to learn

• basic idea

• receive feedback in the form of rewards
• agent's utility is defined by the reward function
• must learn to act so as to maximize expected rewards
• all learning is based on observed samples of outcomes

before: if someone gave me all these values, I could just compute it - I can't compute it anymore, I have to experience the world to identify this

two types

• model based learning
• learn an approximate model based on experiences
• solve for values as if the learned model were correct
• step one: learn empirical MDP model
  • count outcomes \(s'\) for each \(s\) and \(a\)
  • normalize to give an estimate of \(\hat{T}(s, a, s')\)
  • discover each \(\hat{R}(s, a, s')\) when we experience it
• solve the learned MDP
  • for example, use value iteration, as before

def model_based_rl(episodes, gamma):
    counts = {}       # (s, a, s') -> count
    rewards = {}      # (s, a, s') -> observed reward
    for (s, a, s_prime, r) in episodes:
        counts[(s, a, s_prime)] += 1
        rewards[(s, a, s_prime)] = r
    T_hat = {}
    for (s, a, s_prime) in counts:
        total = sum of counts[(s, a, x)] over all x
        T_hat[(s, a, s_prime)] = counts[(s, a, s_prime)] / total
    return value_iteration(mdp_from(T_hat, rewards), gamma, epsilon)

• model-free learning
• I don't need to know \(T\) and \(R\) and I can still get the \(Q\) and \(V\) value
• simplified task: policy evaluation (passive RL)
  • input a fixed policy \(\pi(s)\)
  • you don't know the transitions \(T(s,a,s')\)
  • you don't know the rewards \(R(s,a,s')\)
  • goal: learn the state values
  • the learner is "along for the ride" — no choice about what actions to take, just execute the policy and learn from experience
  • this is NOT offline planning! you actually take actions in the world

direct evaluation

• easy to understand, don't need \(T\) and \(R\), but there are some dependencies between those states, and we need to learn a value from experiencing the world
• it eventually computes the correct average values, using just sample transitions
• so this takes a while — it wastes information about state connections, and each state must be learned separately
• if B and E both go to C under this policy, how can their values be different?

Temporal difference learning

• big idea: learn from every experience
• update \(V\) every time you experience a transition \((s, a, s', r)\)
• likely outcomes \(s'\) will contribute more often
• difference learning of values
• policy is still fixed, still doing evaluation
• move values toward value of whatever successor occurs: running average

Sample of \(V(s)\): \(\text{sample} = R(s, a, s') + \gamma V^\pi(s')\)

Update to \(V(s)\): \(V^\pi(s) \leftarrow (1 - \alpha) V^\pi(s) + \alpha \cdot \text{sample}\)

Same update: \(V^\pi(s) \leftarrow V^\pi(s) + \alpha \big[\text{sample} - V^\pi(s)\big]\)

def td_value_learning(policy, alpha, gamma, episodes):
    V = {s: 0 for s in states}
    for (s, a, s_prime, r) in episodes:
        sample = r + gamma * V[s_prime]
        V[s] = V[s] + alpha * (sample - V[s])
    return V

Problems with TD learning: - TD value learning is a model-free way to do policy evaluation, mimicking Bellman updates with running sample averages - however, if we want to turn values into a (new) policy, we're sunk — policy extraction from \(V\) needs \(T\) and \(R\), which we don't have - idea: learn Q-values, not values. makes action selection model-free too!

Detour: q-value iteration

• value iteration: find successive depth-limited values
• start with \(V_0 = 0\), which we know is right
• given \(V_k\), calculate the depth \(k+1\) values for all states:
• \(V_{k+1}(s) \leftarrow \max_a \sum_{s'} T(s, a, s')\big[R(s, a, s') + \gamma V_k(s')\big]\)

But q values are more useful, so compute them instead - start with \(Q_0(s, a) = 0\), which we know is right - given \(Q_k\), calculate the depth \(k+1\) q-values for all q-states: - \(Q_{k+1}(s, a) \leftarrow \sum_{s'} T(s, a, s')\big[R(s, a, s') + \gamma \max_{a'} Q_k(s', a')\big]\)

the model-free sample version of this is Q-learning:

\(Q(s, a) \leftarrow (1 - \alpha) Q(s, a) + \alpha \big[r + \gamma \max_{a'} Q(s', a')\big]\)

def q_learning(alpha, gamma, episodes):
    Q = {(s, a): 0 for each s, a}
    for (s, a, s_prime, r) in episodes:
        best_next = max over a_prime of Q[(s_prime, a_prime)]
        sample = r + gamma * best_next
        Q[(s, a)] = Q[(s, a)] + alpha * (sample - Q[(s, a)])
    return Q

Probability

full tables

\(P(T, W)\)

T	W	P
hot	sun	0.4
hot	rain	0.1
cold	sun	0.2
cold	rain	0.3

the four operations on a joint table: - summing out (marginalization): \(P(T) = \sum_w P(T, W = w)\) - normalization: divide by \(Z = \sum\) entries so the table sums to 1 - conditional probability / Bayes' rule: \(P(x|y) = \frac{P(x, y)}{P(y)}\), and \(P(x|y) = \frac{P(y|x)P(x)}{P(y)}\) - chain rule: \(P(x_1, x_2, \dots, x_n) = \prod_i P(x_i | x_1, \dots, x_{i-1})\)

conditional independence

\(X\) and \(Y\) are independent iff \(\forall x, y: P(x, y) = P(x)P(y)\)

given \(Z\) we can say that \(X\) and \(Y\) are conditionally independent iff \(\forall x, y, z: P(x, y|z) = P(x|z) P(y|z)\)

(conditional) independence is a property of a distribution

Bayesian Networks

• a DAG: one node per RV
• conditional probability table for each node
• prob of \(X\) given a combination of values for parents
• bayes nets implicitly encode joint distributions as a product of local conditional distributions

• \(P(x_1, x_2, \dots, x_n) = \prod_{i=1}^{n} P(x_i | \text{parents}(X_i))\)

• definition: each node, given its parents, is conditionally independent of all its non-descendants on the graph

• each node, given its Markov blanket, is conditionally independent of all other nodes in the graph
• the Markov blanket refers to the parents, children, and children's other parents

Inference by enumeration

• general case
• evidence variables \(E_1, \dots, E_k\)
• query variable \(Q\)
• Hidden variables \(H_1, \dots, H_r\)
• all variables: \(\{Q\} \cup E \cup H\)

step 1: look at only the entries consistent with the evidence step 2: sum out \(H\) to get the joint of query and evidence step 3: normalize

we end up wanting \(P(Q | e_1, e_2, e_3, \dots)\)

\(P(Q | e_1 \dots e_k) = \frac{1}{Z} \sum_{h_1 \dots h_r} P(Q, h_1 \dots h_r, e_1 \dots e_k)\)

def inference_by_enumeration(bn, Q, evidence):
    table = {}
    for q in domain(Q):
        total = 0
        for h in all assignments to the hidden variables:
            total += bn.joint_probability(Q=q, hidden=h, evidence=evidence)
        table[q] = total
    Z = sum of table.values()
    for q in table: table[q] = table[q] / Z
    return table

if R->T->L whats P(L)?

way 1 — inference by enumeration: build the full joint, then sum out both hidden variables at the end

\(P(L) = \sum_r \sum_t P(r) P(t|r) P(L|t)\)

way 2 — variable elimination: interleave joining and marginalizing so the tables never get big

• join on \(R\): \(P(R, T) = P(R) \cdot P(T|R)\)
• eliminate \(R\): \(P(T) = \sum_r P(r, T)\)
• join on \(T\): \(P(T, L) = P(T) \cdot P(L|T)\)
• eliminate \(T\): \(P(L) = \sum_t P(t, L)\)

both give the same answer; VE never builds a factor bigger than 2 variables here, while enumeration builds the full 3-variable joint first

General Variable Elimination

• query: \(P(Q | E_1 = e_1, \dots, E_k = e_k)\)
• start with initial factors: local CPTs (but instantiated by evidence)
• while there are still hidden variables (not \(Q\) or evidence):
• pick a hidden variable \(H\)
• join all factors mentioning \(H\)
• eliminate (sum out) \(H\)
• join all remaining factors and normalize

def variable_elimination(bn, Q, evidence, ordering):
    factors = [cpt.instantiate(evidence) for cpt in bn.cpts]
    for H in ordering:
        relevant = [f for f in factors if H in f.variables]
        for f in relevant: factors.remove(f)
        joined = pointwise_product(relevant)
        factors.append(joined.sum_out(H))
    result = pointwise_product(factors)
    return result.normalize()

• runtime is dominated by the size of the largest factor produced; the ordering determines that size, and picking a good ordering is hard in general (polytrees always have an efficient one)

independence assumptions in a bayes net

• assumptions we are required to make to define the bayes net when given the graph
• active and inactive paths

active triples (influence flows through): - causal chain \(A \to B \to C\) with \(B\) unobserved - common cause \(A \leftarrow B \to C\) with \(B\) unobserved - common effect \(A \to B \leftarrow C\) with \(B\) or one of its descendants observed

inactive triples (influence is blocked): the complement of each of the above

all it takes to block a path is a single inactive segment

D-separation

• query: is \(X_i \perp X_j \mid \{X_{k1}, \dots, X_{kn}\}\)?
• check all (undirected!) paths between \(X_i\) and \(X_j\)
• if one or more active paths, then independence is not guaranteed
• otherwise (i.e. if all paths are inactive), then independence is guaranteed

topology limits distributions

• given some graph topology \(G\), only certain joint distributions can be encoded
• graph structure guarantees certain conditional dependencies and some independencies
• (there might be more independence)
• adding arcs increases the set of distributions, but has several costs
• full conditioning can encode any distribution

Approximate Inference: Sampling

Prior sampling

instead of having access to the variables, we are going to sample them from the distribution and then produce the net

we are going to sample \(x_i\) from \(P(X_i | \text{Parents}(X_i))\), in topological order

def prior_sample(bn):
    x = {}
    for Xi in bn.variables_in_topological_order:
        x[Xi] = sample from P(Xi | parents assigned in x)
    return x

• consistent: the probability of drawing a given full assignment is exactly the joint probability the BN assigns to it

rejection sampling

we have all the evidence; we are going to sample, if it's not consistent with the evidence, we remove it

def rejection_sample(bn, evidence):
    x = {}
    for Xi in bn.variables_in_topological_order:
        x[Xi] = sample from P(Xi | parents assigned in x)
        if Xi in evidence and x[Xi] != evidence[Xi]:
            return None          # reject: no sample this cycle
    return x

• problem: with unlikely evidence you throw away almost everything

likelihood weighting

fix the evidence variables instead of sampling them, and weight each sample by how likely that evidence was

def likelihood_weighted_sample(bn, evidence):
    x = {}
    w = 1.0
    for Xi in bn.variables_in_topological_order:
        if Xi in evidence:
            x[Xi] = evidence[Xi]
            w = w * P(x[Xi] | parents assigned in x)
        else:
            x[Xi] = sample from P(Xi | parents assigned in x)
    return x, w

• evidence influences the choice of downstream variables, but not upstream ones — that's the limitation

Gibbs sampling

• step 1: fix the evidence (e.g. \(R = +r\))
• step 2: initialize the other variables randomly
• step 3: repeat
• choose a non-evidence variable \(X\)
• resample \(X\) from \(P(X | \text{MarkovBlanket}(X))\)

def gibbs_sample(bn, evidence, steps):
    x = evidence copied, plus a random value for every non-evidence variable
    for i in range(steps):
        X = a non-evidence variable (cycled or chosen at random)
        x[X] = sample from P(X | MarkovBlanket(X) as assigned in x)
    return x

• fixes the upstream problem: you can sample any variable given all the others, so reverse queries work
• successive samples are highly correlated (each depends on the previous), but the procedure is still consistent

Related

• CheatSheet — HS and Berkeley summary sheets for the same material