Task 4

In this assignment, you will investigate fundamental approaches for dealing with the exploration-exploitation trade-off in bandit problems and compare different ways of updating value estimates.

Exercise 1 – Exploration and Exploitation

Open the Exploration vs. Exploitation app.

Open the Exploration vs. Exploitation tool

Choose one of the two contexts Party Opener or Way to School.

First, try to maximize the sum of the rewards you receive by making your own decisions. Use the game mode I decide myself.

Then compare your results with those of an agent in Auto mode.

In particular, investigate:

• What happens if the agent does not explore at all or explores only very little?
• What happens if the agent explores very frequently?
• Why can neither exploring exclusively nor always exploiting the currently best action be optimal in the long run?

Exercise 2 – Methods for Ensuring Exploration

Computer science teacher Ms Hempel is marking the tests of three introductory computer science courses (GK 1, GK 2 and GK 3).

a) Optimistic Initial Values

Ms Hempel is initially “optimistic” and assigns all three courses the initial value

She uses a greedy strategy with optimistic initial values. In the event of a tie, she always chooses a test from the course with the lower course number.

Determine the order in which she marks the first seven tests in each case.

Investigate the following three variants:

1. Sample average: The initial value is , but it does not count as an observation.
2. Constant step size: Use .
3. Pseudo-observation: The initial value is treated as an additional observation when calculating the mean.

Check your solutions using the Bandit Exploration Strategies app.

Open Bandit Exploration Strategies

b) Upper Confidence Bound

Ms Hempel now uses an Upper Confidence Bound method to select the next test to mark.

First, she marks one test from each course. To select the fourth test (), the value

is then calculated for each action.

i) Selecting the Fourth Test

Explain, without carrying out a detailed calculation, why

holds.

Which test is therefore marked fourth?

ii) Selecting the Fifth Test

The fourth test marked is the second test from GK 1. Afterwards, the estimated action values satisfy

Using the selection counts and the exploration term in the UCB formula, explain why a test from GK 2 is selected next.

Exercise 3 – Updating Knowledge Incrementally

a) Calculating the Arithmetic Mean Incrementally

Show by algebraic transformation that for the arithmetic mean of numbers

the following equation holds:

b) Visualizing Incremental Updates

Open the app for incrementally calculating the arithmetic mean.

Open the Incremental Calculation of the Arithmetic Mean tool

Using a suitable example, investigate how the previous mean changes after each new observation.

Pay particular attention to the correction term

and to the factor

Describe how the influence of a single new observation changes as increases.

c) Comparison with Q-Learning

In many value-based reinforcement learning methods, previous value estimates are updated using a new observation.

In tabular Q-learning, the update rule can be written as

Equivalently,

The update of the arithmetic mean can also be written in a form similar to Equation (1):

Compare the update rules.

In particular, address the following questions:

• Which quantity represents the previous knowledge in each case?
• Which quantity contains the new information?
• What role does the weighting factor play?
• How does the factor differ from a constant step size ?
• What additional information is contained in the Q-learning target