Theorem 3.4 (discrete time, corrected): for two bandit processes with discount factors a and b, selecting A or B according as a^t ν_AB(x) > or < b^t ν_BA(y) is optimal
OpenAllocationIndices.two_discount_index_policy_optimalTheorem 3.4. An optimal policy for a simple family of two alternative bandit processes and with discount factors and is one which selects or according as or when is in state and is in state , where
Stated here, in discrete time and corrected. and are Markov bandit processes on countable state spaces with bounded rewards and discount factors ; the family is the two-armed Markov bandit on in which a reward obtained at time from is discounted by and one from by . Let
If a policy selects, in round with in state and in state , whenever and whenever (either when they are equal), then for every initial pair of states its payoff equals the supremum of the payoffs of all policies.
Why the corrections. The printed rule is false. Take two one-state bandits (standard bandits), paying with and paying with . The states never change, so the printed rule, and any rule that depends only on the states, plays one process forever: payoff for or for . Playing for three rounds and then forever earns . The book's proof rescales time so that and share a discount factor ('s step lasts , with reward at process time ). The index of at process time is , and that of is , where . Comparing them is comparing with at the global time . The printed denominator replaces the common by for one process and for the other. Nash's generalized-bandit route on p. 66, with and , gives the same indices. Checked against brute-force dynamic programming on 150 random instances (up to three states per process, rewards of both signs): the corrected rule is optimal from every initial state, while the printed rule and its discrete analogue with denominator are strictly suboptimal in 215 initial states.
import Definitions.Def_AllocationIndices_Jobs open MeasureTheory ProbabilityTheory BanditAlgorithm
namespace AllocationIndices
theorem two_discount_index_policy_optimal {SA SB : Type*} [MeasurableSpace SA] [Countable SA]
[MeasurableSingletonClass SA] [MeasurableSpace SB] [Countable SB] [MeasurableSingletonClass SB]
(PA : Kernel SA SA) [IsMarkovKernel PA] {rA : SA → ℝ} (hrA : BoundedReward rA)
(PB : Kernel SB SB) [IsMarkovKernel PB] {rB : SB → ℝ} (hrB : BoundedReward rB)
{a b : ℝ} (ha0 : 0 < a) (ha1 : a < 1) (hb0 : 0 < b) (hb1 : b < 1)
{π : MarkovBanditPolicy 2 (SA ⊕ SB)} (hπ : IsTwoDiscountIndexPolicy PA PB rA rB a b π)
(x : SA) (y : SB) :
twoDiscountValue PA PB rA rB a b π x y =
⨆ π' : MarkovBanditPolicy 2 (SA ⊕ SB), twoDiscountValue PA PB rA rB a b π' x y := by sorry
end AllocationIndices
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.