Action Selection in Bandit Problems
q∗(a) denotes the true value of action a.
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.
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
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.
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
Identifying the Meaning of Qt(a)
Suppose an expression is written as Qt(a). Identify what each symbol tells you.
Find a: The symbol a identifies the action whose value is being discussed.
Find Q: The Q indicates that the expression is an estimate rather than the notation q∗(a) for the true value.
Find t: The subscript t identifies the time of the estimate.
Combine the parts: Qt(a) means the estimate at time t of the true value q∗(a).
Qt(a) is a time-indexed estimate for the true value of action a.
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
Treating q∗(a) and Qt(a) as interchangeable.
q∗(a) denotes the true value, whereas Qt(a) denotes an estimate of that true value at time t.
Fix:
Ask whether the notation contains the star or the time subscript. The star marks the true value; the subscript marks the estimate's time.Ignoring the time index in Qt(a).
The subscript t identifies the time of the estimate.
Fix:
Read Qt(a) as the estimate at time t of q∗(a).Assuming that t identifies the action.
The symbol a identifies the action in both q∗(a) and Qt(a).
Fix:
Use a to identify the action and t to identify the time of the estimate.
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
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.
- 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.