Chapter 2 Notes

Numerics from example runs

Run 1

Greedy policy

• Pure exploitation
• No exploration
• Got lucky because $a_1$ was best action and it was selected by arg-max on first iteration

$\varepsilon$-Greedy policy with $\varepsilon = 0.1$

• Exploration and exploitation evident

Run 2

Greedy policy

• Pure exploitation
• No exploration
• Failed to find the best action $a_7$ because no exploration
• Spent most of its actions on $a_4$ which was the best action that had been seen in early stages of averaging

$\varepsilon$-Greedy policy with $\varepsilon = 0.1$

• Exploration and exploitation evident
• Found the best action $a_7$ through exploration and then exploited it

Observation

Based on these example runs, we can see why the final long term (after 1000 steps) reward of $\varepsilon$-greedy policy is greater than for the pure greedy policy, though the opposite can be true in the short term (first 10-20 steps).

Matlab code for testbed

xxxxxxxxxx
K = 10; % Number of arms
N = 1000; % Number of steps per run
M = 2000; % Number of runs
Rave = zeros(N,1);
for m = 1:M
    q = randn(K,1); % True action value
    Q = zeros(K,1); % Estimated action value
    C = zeros(K,1); % Counts
    D = zeros(K,1); % Accumulated reward
    for n = 1:N
        % epsilon-greedy policy
        epsilon = 0.1;
        u = rand(); % Draw random number U[0,1]
        if(u > epsilon)
            [~,a]=max(Q); % Exploitation (greedy) action
        else
            a = randi([1,K],1); % Exploration (random) action
        end
        R = q(a) + randn(); % Draw reward at random from PDF depending on action
        D(a) = D(a) + R; % Accumulate reward
        C(a) = C(a) + 1; % Increment count
        Q(a) = D(a)/C(a); % Update estimated value
        Rave(n) = Rave(n) + R;
    end
end