hash table are a randomized data structure that allows fast insert / delete / search.

• insert: stick it into the data structure based on key
• delete: delete from data structure
• search: get a pointer into the data structure, or null

\(O\qty(1)\) time insert, delete, and search

constituents

• \(U\) is a universe, where \(|U| = M\)
• \(K \subseteq U\) keys are going to show up, \(|K| = n\)
• \(M \gg n\)
• \(h: U \to \qty {1 \dots n}\) is a function that maps elements of \(U\) to buckets

slight abuse of notation: there will be \(n\) buckets, and \(n\) elements that come in. They should be similar OOM but can be not equal (since you can stick multiple into a bucket and run a constant-time search).

• \(\mathcal{P}\) problem (states, transitions, etc.)
• \(N\) visit counts
• \(Q\) a q-table: action-value estimates
• \(d\) depth (how many next states to look into)—more is more accurate but slower
• \(U\) value function estimate; usually a Rollout Policy, estimate at some depth \(d\)
• \(c\) exploration constant

After \(n\) simulation s from the starting state; we find the best action for our current state from our q-table.

Subroutine: simulate(state, depth_remaining)

• If depth_remaining=0, simply return the utility from the value function estimate
• For some s, Actions that we just got, if we haven’t seen it, we just return the value function estimate + initialize the N and Q tables
• select an action via the monte-carlo exploration formula
• sample a next state and current reward based on the action you gotten via a generative model
• value = reward + discount*simulate(next_state, depth_remaining-1)
• add to the N(state, action) count
• update the q table at (state, action): Q[s,a] + = (value-Q[s,a])/N[s,a] (“how much better is taking this action?” — with later times taking this action more heavily discounted)

monte-carlo exploration

\begin{equation} \max_{a} Q(s,a) + c \sqrt{ \frac{\log \sum_{a}N(s,a)}{N(s,a)}} \end{equation}

Key Sequence

Notation

New Concepts

• hashing
  • direct addressing
  • hash families

Important Results / Claims

Questions

Interesting Factoids

Key Sequence

Notation

New Concepts

• boosting
  • AdaBoost

Important Results / Claims

Questions

Interesting Factoids

Review! Probability

Let \(A_1 …, A_{M}\) be independent events, each with probability \(p\). Let \(T = \sum_{i=1}^{n} A_{i}\), meaning \(T \sim \text{Bin}\qty(n,p)\). \(\mu = \mathbb{E}\qty[T] = np\).

Two facts:

Markov bound

;

Chebyshev’s inequality

Pairwise Independence

see Universal Hash Family

Gouldwasser-Sipsr

• ⟸
• ⟵
• 18
• 19
• 20
• 21
• 22
• ⟶
• ⟹