# CS188 Notes Part 1
Final notes can be found [here](https://hackmd.io/@matthewtang/188-final)
# Lecture 1: 8/29/19

## Designing Rational Agents
* Agent - entity that perceives and acts
* Rational agent- select actions to max utility
* Percepts, environment, action space dictate techniques for rational actions

# Lecture 2: 9/3/19
* Reflex agents - choose action based on current precept (maybe memory)
* Do not consider future consequences of actions
* Consider how the world **is**
* Planning agents - make decisions based on hypothesized consequences of actions
* Needs model of how world evolves in response to actions
* Formulate a goal
* Consider how world **would be**
* Optimal vs complete planing
* Completeness - tell us if no solution exists
* Planning vs replanning
* Tradeoff of time for more complicated planning agents

## Search problems
* State space
* Successor function (with actions, costs)
* A start state and a goal test
* A solution is a sequence of actions (a plan) which transforms the start state to a goal state

### Example Traveling in Romania
* State space: cities
* Don't want too many states
* Successor function: raods - go to adjacent city. cost = distance
* Start state: Arad
* Goal test: Is state == Bucharest?
* Solution: TBD

### Example: State Space Sizes
* World state:
* Agent positions: 120
* Food count: 30
* Ghost positions: 12
* Agent facing: NSEW
* Total world states: $120(2^{30})(12^2)4$
* Total states for pathing: $120$
* Only need to keep track of agent positions
* States for eat all dots: $120(2^{30})$
* Depending on the problem, your state space will be a subset of world state

### Example: Safe Passage
* Boolean consumption for big and small dots
* Remaining time for scared ghosts
* Goal test must work on state

## State Space Graphs
* Mathematical representation of a search problem
* Nodes are world configurations
* Arrows are successors (action results)
* Goal test is a set of goal nodes
* In a search graph, each state only occurs once
* Takes too much memory to explicitly construct this

## Search Trees
* A "what if" tree and their outcomes
* Root node: start state
* Children: successors
* Nodes corresponds to plans that achieve those states
* Can't build the whole tree for problems

## General Tree Search
* Fringe, expansion, exploration strategy
* Main idea: which fringe nodes to explore?

# Lecture 3: 9/5/19

## Search Algorithm Properties
* Complete: Guaranteed to find a solution if one exists?
* Return in finite time if not?
* Optimal: Guaranteed to find least cost path?

### Depth First Search
* Stack (LIFO)
* Time complexity
* Total number of nodes: $O(b^m)$ nodes where b is branching factor, m is the depth
* Space complexity
* $O(bm)$
* Complete if no cycles
* Not optimal

### Breadth First Search
* Fringe/queue (FIFO)
* Processes all nodes above shallowest solution
* Time: $O(b^s)$ where b is branching factor, s is depth of shallowest solution
* Space: $O(b^s)$
* Complete: Yes, guaranteed to return a solution if exists
* Optimal: No

### Iterative Deepening
* Combine BFS and DFS.
* Get DFS space advantage with BFS time
* Run DFS with depth limit 1. If no solution, increase limit by 1.
* Early depths have redundant searches but it's not too bad since the last levels take the most time (exponential)

### Uniform Cost Search
* Fringe is a priority queue (priority is cumulative cost)
* If solution costs $C^*$ and arcs cost at least $\epsilon$, effective depth is $\frac{C^*}{\epsilon}$
* Time: $O(B^{C^* / \epsilon})$
* Space: $O(B^{C^* / \epsilon})$
* Complete: If solution has a finite cost and minimum cost arc is positive, yes
* Optimal: yes
* Downsides:
* Explores options in every "direction"
* No information about end goal

## Informed Search
* Heuristics
* Estimate how close a state is to a goal
* Ex. Manhattan distance (ignore walls), euclidean distance
* Greedy Search
* Expand the node that seems closest
* Commonly takes you in a suboptimal route
* $A^*$
* Combining UCS and Greedy
* UCS orders by path cost, backwards cost - $g(n)$
* Greedy orders by goal proximity, forwards cost - $h(n)$
* Add $g(n) + h(n)$
* Stop when goal is dequeued
* Heuristic estimates need to be less than the actual costs
* Inadmissible(pessimistic) heuristics overestimate
* Admissible(optimistic) if $o \leq h(n) \leq h^*(n)$ where $h^*(n)$ is the true cost to ta nearest goal
* Often admissible heuristics are solutions to relaxed problems where new actions are available
* Inadmissible heuristics are useful too to find a solution faster
* Ex. For 8 puzzle
* Heuristic: number of misplaced tiles (terrible)
* Better heuristic: Manhattan distance of each tile
* Graph Search

### Graph Search
* Don't expand a state twice
* Tree search + a set of expanded states
* Consistency of heuristic - heuristic "arc" cost $\leq$ actual cost for each arc
* With admissible heuristic, Tree A* is optimal
* With consistent heuristic, Graph A* is optimal

# Lecture 4: 9/10/19

## Constraint satisfaction problems (CSP)
* $N$ variables, domain $D$ of all colors
* Constraints - restrictions on values of variables in regard to other variables
* Planning: for planning a sequence of actions (path) to a goal
* Paths have various costs, depths
* Difficult to plan low cost path, goal is easy to determine
* Identification: Assignments to variables
* Goal itself is important, not the path
* All paths at the same depth (for some formulations)
* CSPs are specialized for identification problems
* State is a "black box"/ arbitrary data structure
* Goal test can be a function over states
* Successor can be anything
* CSP
* A special subset of search problems
* State is defined by variables $X_i$ with values from a domain D (sometimes D depends on i)
* Goal test is a set of constraints

### Example: Map Coloring
* Variables: WA, NT, Q, NSW, V, SA, T
* Domains: $D = \{red, green, blue\}$
* Constraints: Adjacent regions must have diff colors
* Implicit: $WA \neq NT$
* Explicit: $(WA, NT) \in \{ (red, green), (red, blue), \ldots \}$

## Backtracking Search
* BFS is no good, DFS is better but still not good
* Idea: Incremental goal tests - check constraints along the way
* Idea: Fix one variable and then do dfs
* Backtracking = DFS + variable-ordering + fail-on-violation
* Filtering - Keep track of domains for unassigned variables, cross off bad options
* Forward checking: Cross off values that violate a constraing when adding new assignment
* Constraint Propagation: Propagates info from assigned to unassigned variables.
* Thinks about effects at deeper levels
* Arc consistency: Property such that every x in the tail has a y that could be assigned without violating a constraint
* Delete from the tail to make consistent

# Lecture 5: 9/12/19

## Filtering
* Forward checking
* Cross off values that violate a constraint when added to the existing assignment
* K consistency - for every k nodes, there exists a consistent assignment
* 1-Consistency: Check each single node
* 2-Consistency: Arc consistency
* Strong K-consistency: Also means $k-1, \ldots, 2, 1$ consistent
* Strong N-consistent means no need for backtracking

## Ordering
* Variable Ordering:
* Minimum Remaining Value (MRV) - Choose the variable with the fewest legal left values in its domain
* Aka "most constrained"
* Value Ordering:
* Least constrained value - Given a chosen variable, choose an assignment that is least constraining

## Iterative Improvement
* While not solved:
* Variable selection: randomly select any conflicted variable
* Value selection: min-conflicts heuristic
* Choose a value that violates the fewest constraints
* Very good performance except for a golden ratio R

## Structure
* Independent subproblems are identifiable as connected components of constraint graph
* If the constraint graph is a tree (no loops), can be solved in $O(nd^2)$ as opposed to $O(d^n)$
* $d^2$ comes from checking everything at head and tail

### Tree CSPs
* Choose a root variable, order variables so that parents precede children
* 1. Do a single pass backwards from n to the 2nd node to ensure the arcs pointing to those nodes are consistent
* All root to leaf arcs are consistent
* Each X-> Y was consistent at one point and Y's children were always processed first so Y's domain cannot be reduced later
* 2. Assign forward: for 1 to n, assign consistently
* No need to backtrack

### Nearly Trees
* Conditioning - Instantiate a variable, prune neighbors domains
* Cutset conditioning - Pick a node, assign it all possible ways, solve the remaining tree
* Cutset size c, total time $O(d^c (n-c)d^2)$
* Very fast for small c
* Tree Decomposition
* Idea: create a tree-structured graph of mega-variables
* Each mega-variable encodes part of the original CSP
* Subproblems overlap to ensure consistent solutions

## CSP Summary
* Basic solution: Backtracking search
* Improvements:
* Ordering
* Filtering
* Structure
* Iterative min-conflicts is often most practical

## Local Search
* Tree search keeps unexplored alternatives on the fringe (ensures completeness)
* Local search: improve a single option until you can’t make it better (no fringe!)
* Successor function is local changes now
* Better time and memory, but incomplete and suboptimal
* Idea: Start wherever, move to best neighboring state
* If no better neighbors, quit

### Simulated Annealing
* Escape local maxima by allowing downhill movement
* But more rare as time goes on
* $T$, a "temperature" controls the probability of downward steps
* If $T$ is decreased slow enough, will converge on optimal solution

### Genetic Algorithms
* Natural selection strategy
* Keep best N hypotheses at each step (selection) based on a fitness function
* Pairwise crossover operators, with optional mutation to give variety

# Lecture 6: 9/17/19

## Search with other agents
* Types of games:
* Deterministic or stochastic?
* 1, 2, or more players?
* 0 sum?
* Perfect information (can you see the state?)
* Sometimes have to estimate the state from sensor input
* Do we know the objectives/utilities of the other agents?
* For now, assume that we know their objectives exactly.

## Types of games
* General games
* Agents have independent utilities
* Cooperation, indifference, competition are possible
* Zero-sum games
* Agents have opposite utilities
* One maximizes, other minimizes
* Adversarial, pure competition

## Deterministic Games with Terminal Utilities
* States: $S$
* Players: $P = \{1 \ldots N\}$ (usually take turns)
* Actions: $A$ (can depend on player/state)
* Transition function: $SxA \implies S$
* Terminal Test: $S \implies \{t,f\}$
* Terminal Utilities: $SxP \implies R$
* Solution for a player is a policy $S \implies A$
* No longer minimizing cost, agent tries to maximize score/utility
* Value of a state: best achievable outcome/utility from that state
* Non-terminal states: $V(x) = \max(V(x'))$

## Minimax Adversarial Search
* Deterministic, zero-sum games
* One player maximizes result, other minimizes result
* Minimax search
* State-space search tree
* Players alternate turns
* Compute each node's minimax value- best achievable utility against a rational, optimal adversary

def value(state):
  if state is terminal: return state utility
  if next agent is MAX: return max-value(state)
  if next agent is MIN: return min-value(state)

* Time: $O(b^m)$, Space: $O(bm)$
* But we don't need to explore the whole tree

## Alpha-Beta Pruning
* Node $n$ has children
* Stop considering options better/worse than one already found (depending on who is pruning)
* Good child ordering improves pruning effectiveness
* Perfect ordering - Time: $O(b^{m/2})$
* Doubles solvable depth
* Metareasoning - computing what to compute

# Lecture 7: 9/19/19

## Resource Limits
* Cannot realistically search to leaves
* Solution: Depth limited search
* Evaluation function - estimate/score non-terminals in depth limited search
* Ex. Weighted linear sum of features
* Depth matters:
* The deeper in the tree the eval function is, quality matters less
* Tradeoff between complexity of features and computation

## General Sum Games
* "Maximax" games where terminals have utility tuples
* Each player maximizes its own component
* Sometimes you get competition, sometimes collaboration

## Expectimax Search - Uncertain Outcomes
* Explicit randomness, unpredictable opponents/humans
* Reflect average-case instead of worst case
* Compute average score under optimal play
* Calculate expected utilities (weighted average of children)
* Aka Markov Decision Process (MDP)
* Cannot prune
* Probabilities can be uniform distribution or sophisticated

# Lecture 8: 9/24/19

## Markov Decision Processes
* Use when world is stochastic or you don't know the whole world in your model
* Ex. Noisy movement in a grid world
* Agent receives rewards at each time step
* Small living reward at each step (can be negative)
* Big rewards at the end (good or bad)
* Goal: maximize sum of rewards
* Expectimax is a naive tool to solve
* Given the present state, future and past are independent
* Action outcomes depend on only current state

## MDP Formulation
* 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)$
* Aka Model/dynamics
* Reward function $R(s, a, s')$
* Sometimes just $R(s)$ or $R(s')$
* Start state
* Terminal state
* Policy = choice of action for each state
* Utility = sum of (discounted) rewards

## Policies
* In deterministic single agent search, we have an optimal plan
* For MDPs we want an optimal policy $\pi^*: S \rightarrow A$
* Policy $\pi$ gives action for each state
* Optimal policy maximizes expected utility
* Explicit policy = reflex agent
* Too small of a living cost in reward function can cause agent to get stuck in local minima
* Too large can cause agent to "end suffering"

## Discounting
* Maximize sum of rewards but prefer rewards earlier
* Solution: Exponential decay of value later on
* Discount factor $\gamma$
* Think of it as a gamma chance of ending the process at each step
* Helps algorithms converge

## Infinite Utilities
* Finite horizon (similar to depth-limited search)
* Terminates after fixed T steps (life)
* Give nonstationary policies ($\pi$ depends on time left)
* Discounting factor $0 < \gamma < 1$
* Converging geometric series
* $\gamma = 0$ only cares about current state reward (not practical)
* $\gamma > 1$ makes things in the future worth more
* Smaller $\gamma$ means smaller "horizon"/focus

# Lecture 9: 9/26/19

## Bellman Equation
* Q values have a value for every possible action
* Recursive definition of value: $V^* = \max\limits_a Q^*(s,a)$
* Best possible reward of all possible actions to take
* $Q^*(s,a) = \sum\limits_{s'} T(s,a,s')[R(s,a,s')+ \gamma V^*(s')]$
* Best possible reward given an action at current state
* $V^*(s) = \max\limits_a \sum\limits_{s'} T(s,a,s')[R(s,a,s')+ \gamma V^*(s')]$

## Time-Limited Values
* Define $V_k(s)$ to be optimal value of s if game ends in k more time steps
* Equivalent to depth-k expectimax

## Value Iteration
* $V_0(s) = 0$ b/c no time steps left so no reward
* $V_{k+1}(s) = \max\limits_a \sum\limits_{s'} T(s,a,s')[R(s,a,s')+ \gamma V_k(s')]$
* Repeat until convergence
* Problems:
* Complexity of iterations: $O(S^2A)$
* Max at each state rarely changes
* Policy often converges before values do

### Convergence
* If tree has maximum depth M, $V_M$ holds actual untruncated values
* If $\gamma < 1$, the values converge as k increases

### Computing Actions from Values
* Do a mini-expectimax of 1 step
* $\pi^*(s) = \text{argmax}_a \sum\limits_{s'} T(s,a,s')[R(s,a,s')+ \gamma V_k(s')]$

## Policy Iteration
* 1) Policy evaluation - calculate utilities for a fixed policy until convergence
* 2) Policy improvement - update policy using 1 step look ahead with resulting converged (but not optimal) utilitieis as future values
* Repeat until policy converges
* If we fixed a policy $\pi(s)$, only 1 action per state
* Compute utility of state s under a fixed (usually not optimal) policy
* Define utility of state s under fixed policy $\pi$ as:
* $V^\pi(s) =$ expected total discounted rewards starting in s, following $\pi$
* Recursive relation doesn't need to use max since we use $\pi(s)$ instead of optimal action
* Evaluation: Find values with policy evaluation and iterate until values converge
* Improvement: Get a better policy using policy extraction

## Comparison
* Both value and policy iteration compute same thing
* Value iteration:
* Every iteration updates both values and implicity policy
* Don't track plicy but taking max over actions implicitly recomputes it
* Policy Iteration
* Several passes that update utilities with fixed policy
* After policy is evaluated, a new policy is chosen
* New policy improves

# Lecture 10: 10/1/19
## Reinforcement Learning
* Missing information about MDP so you can't make an optimal policy
* Exploitation: Use what you know eventually
* Regret: Even if you learn intelligently, you make mistakes
* Sampling: Have to try things repeatedly b/c of chance
* Difficulty: Learning is much harder than solving a known MDP
* Exploration: you have to try unknown actions to get information
* Looking for a policy $\pi(s)$
* We don't know T or R
* Don't know which states are good or what actions do
* Can no longer take actions offline since we don't know T or R
* Not a POMDP since you know the output (is observable)

## Passive Reinforcement Learning
* Model-Based Idea
* Idea: We eventually learn the right model
* Learn an approximate model based on experiences
* Solve for values as if learned model was correct
* 1) Learn empirical MDP model
* Count outcomes $s'$ for each action, normalize
* Discover rewards from actions
* 2) Solve the learned MDP (Ex. via value iteration)

## Model-Free
* Idea: Samples appear with the right frequencies
* Simplified task: policy evaluation
* Input a fixed policy $\pi(s)$, don't know T or R
* Goal: Learn state values
* Learner is "along for the ride"
* No choice about what actions to take
* Execute policy and learn from the experience

### Direct Evaluation
* Compute values for each state under $\pi$
* Average together observed sample values
* Instead of trying to learn a transition function, just find values for states
* Pros: Don't need to understand T or R, eventually computes correct average values
* Cons: Wastes info about state connectivity, takes a while to learn each state

## Temporal Difference Learning
* Update $V(s)$ each time we experience a transition
* Likely outcomes $s'$ contribute updates more often
* Sample: $R(s, \pi(s), s') + \gamma V^\pi (s')$
* Update: $V^\pi(s) \leftarrow (1- \alpha)V^\pi(s) + (\alpha)sample$
* Aka $V^\pi(s) \leftarrow V^\pi(s) + \alpha(sample - V^\pi(s))$
* Exponential moving average
* We forget about the past since more recent is more representative
* Problem: We can't turn values into a new policy
* Solution: Learn Q-values, not values

## Q-Value Iteration
* Value Iteration (from before): Find successive (depth limited) values
* Start with $V_0(s) = 0$
* Given $V_k$, calculate depth $k+1$ values for all states
* Q-Value Iteration:
* Start with $Q(s,a) = 0$
* $Q_{k+1}(s,a) = \sum\limits_{s'}T(s,a,s')[R(s,a,s') + \gamma \max\limits_{a'}Q_k(s',a')]$

## Q-Learning
* Sample based Q-value iteration
* Learn $Q(s,a)$ values as you go
* Receive a sample $(s,a,s',r)$
* Incorporate new estimate into a running average
* Converges to optimal policy even if you act suboptimally
* Have to explore enough
* Make learning rate small but not decrease too quickly

# Lecture 11: 10/3/19
## Summary
* Known MDP - Offline solution
* Compute $V^*, Q^*, \pi^*$ - Value/policy iteration
* Evaluate fixed policy $\pi$ - Policy iteration
* Unknown MDP - Model-based
* Compute $V^*, Q^*, \pi^*$ - Value/policy iteration on approx MDP
* Evaluate fixed policy $\pi$ - Policy iteration on approx MDP
* Unknown MDP - Model-free
* Compute $V^*, Q^*, \pi^*$ - Q-Learning
* Evaluate fixed policy $\pi$ - Value Learning
* Active Reinforcement Learning
* Act according to current optimal (based on Q-Values) but also explore
* Use the feedback it receives to iteratively update its policy while learning until eventually determining the optimal policy after sufficient exploration

## Exploration vs Exploitation
* $\epsilon$ greedy - With a small probability $\epsilon$ act randomly, with large probability $1-\epsilon$
* Problems: Keep thrashing once learning is done
* Solution: Lower $\epsilon$ over time or have exploration functions
* Exploration functions
* Explore areas that we aren't that certain are bad, but eventually stop
* Take a value estimate $u$ and visit count $n$ and return an optimistic utility like $f(u,n) = u + k/n$
* Modified Q updates propagate "bonus" back to states that lead to unknown states

## Regret
* Measure of total mistake cost: difference between your rewards (including old suboptimality) and optimal rewards
* Minimizing regret requires optimally learning to be optimal
* Random exploration tends to have high regret
* Can never have 0 regret unless given a known optimal policy
* Or could define regret relative to the best of a class of learning algorithms

# Lecture 12: 10/8/19

## Approximate Q-Learning
* Basic Q-Learning keeps a table of q-values
* Too many states to visit them all in training and hold in memory
* Want to generalize learning from small number of training states to new similar states
* Fundamental idea in ML
* Solution: Describe a state using a vector of properties
* Features: functions from states to real numbers (often 1 or 0) to capture important properties of states
* Ex. Dist to closest ghost, food, num ghosts, 1/dist^2
* Linear Value functions
* $V(s) = w_1f_1(s) + w_2f_2(s) + \ldots w_nf_n(s)$
* Advantage: experience is summed up in a few powerful nums
* Disadvantage: States can share features but actually be very diff in value
* Approximate Q-Learning
* $Q(s, a) = w_1f_1(s, a) + w_2f_2(s, a) + \ldots w_nf_n(s, a)$
* difference = $[r + \gamma \max\limits_{a'} Q(s', a')] - Q(s,a)$
* $Q(s,a) \leftarrow Q(s,a) + \alpha[\text{difference}]$
* $w_i \leftarrow w_i + \alpha[\text{difference}]f_i(s,a)$
* Adjust weights of active features.
* If something bad happens, blame the features that were present

## Least Squares
* Total error $= \sum\limits_i (y_i - \hat{y_i})^2 = \sum\limits_i \left(y_i - \sum\limits_k w_kf_k(x_i)\right)^2$
* $error(w) = \frac{1}{2}\left(y - \sum\limits_k w_kf_k(x_i)\right)^2$
* $\frac{\partial{error(w)}}{\partial{w_m}} = -\left(y - \sum\limits_k w_kf_k(x_i)\right)f_m(x)$
* By chain rule
* $w_m \leftarrow w_m + \alpha \left(y - \sum\limits_k w_kf_k(x_i)\right)f_m(x)$
* $w_m \leftarrow w_m + \alpha[r + \gamma \max\limits_{a'} Q(s', a') - Q(s,a)]f_m(s,a)$
* target - prediction

## Policy Search
* Problem: Feature-based policies that work well don't approximate V/Q best
* Q learning priority: get Q-values close (modeling)
* Action selection priority: Get ordering of Q-values right (prediction)
* Solution: learn policies that maximize rewards, not the values that predict them
* Policy search: Start with an ok solution (e.g. Q-learning) then fine-tune by hill climbing on feature weights

## Model-based vs Model-free
* Model-based
* Model is nice to learn thru reward functions
* Learning values is more complicated than learning dynamics
* Model-free
* Good if dynamics are complicated