• \(\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

• ⟸
• ⟵
• 57
• 58
• 59
• 60
• 61
• ⟶
• ⟹