L8 - Exploring Exploration

Question 1

K-Armed Bandit

Answer 1

K agents, each with an arm to pull that has a probability of reward that is unknown

Question 2

Maximum likelihood Strategy

Question 3

What is the maximum confidence strategy and where does it fail.

Answer 3

The maximum liklihood strategy will always pick the agent or arm that has been chosen the most as we have the highest confidence of the outcome.

Question 4

What is the Minimum Confidence strategy. How does it fail.

Answer 4

The Minimum Confidence is purely exploration and will always choose the bandit that has been chosen the least.

Question 5

What are the metrics for bandits?

Answer 5

Bad metrics

1. Identify optimal arm in the limit.
2. Maximize the (discounted) expected reward.
   
   1. Gittins Index - only works for bandit problems
3. Maximize expected reward over finite horizon.

Good metrics

1. Identify near optimal arm with high probability (1- delta) in time t(k,epsilon,delta) 0 poly time - PAC / PAO
2. nearly maximize rewward with high probability (1- delta) in time t(k,epsilon,delta) 0 poly time - PAC / PAO
3. Pull a non near optimal arm no more than t(k,epsilon,delta) with high probability (1- delta)

Question 6

What is the R_Max algortihm

Answer 6

1. Keep track of the MDP
2. Any unkown state-action pair is assumed to be R-Max (maximum possible reward)
3. Solve the MDP
4. Tack action from π*

Question 7

What is the General Rmax Algorithm

Answer 7

1. Keep track of the MDP
2. Any unkown state-action pair is assumed to be R-Max (maximum possible reward)
   
   1. unkwon s,a if tried fewer than c times,
   2. Then use Maximum Likelihod estimate
3. Solve the MDP
4. Tack action from π*

a

Question 8

Hoeffding Bound

Answer 8

answer

Question 9

Simulation Lemma

Answer 9

Answer

Question 10

Explore or Exploit Lemma

Answer 10

It all transistion are either accurately estimated or unknown, the optimal policy is either near optimal or an unkown state is reached quickly.