Action Selection in Bandit Problems

The same action identifier a appears in both expressions. The difference is that q∗(a) denotes the true value, while Qt(a) denotes an estimate of that true value at time t.

Programming

Two Values for One Action

When discussing an action in a bandit problem, it is important to distinguish the action's true value from an estimate of that value. The true value is written q∗(a). An estimate at a particular time is written Qt(a). These expressions refer to closely related ideas, but they are not the same quantity.

What is the difference between the fixed true value q∗(a) and the estimate Qt(a) for the same action?

Key point

The same action identifier a appears in both expressions. The difference is that q∗(a) denotes the true value, while Qt(a) denotes an estimate of that true value at time t.

Reading the Symbols

Definition

In q∗(a), a identifies the action and the star distinguishes the true value of that action. In Qt(a), a still identifies the action, while the subscript t identifies the time of the estimate.

How do the action identifier a and the time index t map to the true value q∗(a) and the time-dependent estimate Qt(a)?

The notation can be read in two stages. First, identify which action is being discussed by looking at a. Then identify whether the expression refers to the true value or an estimate. The star in q∗(a) marks the true value. The subscript t in Qt(a) marks the time associated with the estimate.

Following an Estimate Through Time

Worked example

Identifying the Meaning of Qt(a)

Suppose an expression is written as Qt(a). Identify what each symbol tells you.

1
Find a
The symbol a identifies the action whose value is being discussed.
2
Find Q
The Q indicates that the expression is an estimate rather than the notation q∗(a) for the true value.
3
Find t
The subscript t identifies the time of the estimate.
4
Combine the parts
Qt(a) means the estimate at time t of the true value q∗(a).

Result

Qt(a) is a time-indexed estimate for the true value of action a.

How does the notation identify an estimate for the same action at different time steps?

In this timeline, the action identifier a remains the same while the time index changes. The notation therefore distinguishes an estimate associated with one time from an estimate associated with another time. The symbol t does not identify a different action; it identifies when the estimate is being considered.

Common Notation Mistakes

Common mistake
Treating q∗(a) and Qt(a) as interchangeable.
What it looks like
Reading both expressions as simply the value of action a.
Why it fails
q∗(a) denotes the true value, whereas Qt(a) denotes an estimate of that true value at time t.
Do this instead
Ask whether the notation contains the star or the time subscript. The star marks the true value; the subscript marks the estimate's time.
Common mistake
Ignoring the time index in Qt(a).
What it looks like
```
Reading Qt(a) without considering t.
```
Why it fails
The subscript t identifies the time of the estimate.
Do this instead
```
Read Qt(a) as the estimate at time t of q∗(a).
```
Common mistake
Assuming that t identifies the action.
What it looks like
Interpreting the subscript t as another action label.
Why it fails
The symbol a identifies the action in both q∗(a) and Qt(a).
Do this instead
Use a to identify the action and t to identify the time of the estimate.

Best practice

When reading either expression, name the action first, then classify the value notation. For q∗(a), say “the true value of action a.” For Qt(a), say “the estimate at time t of the true value of action a.”

Notation Check

EASY

For each expression, identify the action, identify whether it represents a true value or an estimate, and identify the time information if it is present: q∗(a) and Qt(a).

Hints

The symbol a identifies the action in both expressions.
Look for the star to identify the true value.
Look for the subscript t to identify the time of an estimate.

Your attempt (not saved)

1
The essential distinction is simple: q∗(a) denotes the true value of action a, while Qt(a) denotes an estimate at time t of that true value. The symbol a identifies which action is under discussion. The star distinguishes the true value, and the subscript t identifies the time of the estimate.

Key Takeaways

q∗(a) denotes the true value of action a.
Qt(a) denotes the estimate at time t of q∗(a).
The symbol a identifies the action in both expressions.
The star distinguishes the true value, while the subscript t identifies the time of an estimate.
A true value and an estimate of that value should not be treated as the same quantity.

More concepts starting with A