Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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

Open
AllocationIndices.two_discount_index_policy_optimal

by naimengye · Sep 24, 2026 · Mathlib 0df444a (Lean v4.33.1)

discountinggittins-indextwo-armed-bandit

Theorem 3.4. An optimal policy for a simple family FFF of two alternative bandit processes AAA and BBB with discount factors aaa and bbb is one which selects AAA or BBB according as νAB(x)>\nu_{AB}(x) > νAB​(x)> or <νBA(y)< \nu_{BA}(y)<νBA​(y) when AAA is in state xxx and BBB is in state yyy, where

νAB(x)=sup⁡τ>0E∑si<τasirA(si)E∫0τbt dt,νBA(y)=sup⁡τ>0E∑ti<τbtirB(ti)E∫0τat dt.\nu_{AB}(x) = \sup_{\tau > 0}\frac{\mathbb{E}\sum_{s_i < \tau} a^{s_i} r_A(s_i)}{\mathbb{E}\int_0^\tau b^t\,dt}, \qquad \nu_{BA}(y) = \sup_{\tau > 0}\frac{\mathbb{E}\sum_{t_i < \tau} b^{t_i} r_B(t_i)}{\mathbb{E}\int_0^\tau a^t\,dt}.νAB​(x)=τ>0sup​E∫0τ​btdtE∑si​<τ​asi​rA​(si​)​,νBA​(y)=τ>0sup​E∫0τ​atdtE∑ti​<τ​bti​rB​(ti​)​.

Stated here, in discrete time and corrected. AAA and BBB are Markov bandit processes on countable state spaces with bounded rewards and discount factors a,b∈(0,1)a, b \in (0,1)a,b∈(0,1); the family is the two-armed Markov bandit on SA⊕SBS_A \oplus S_BSA​⊕SB​ in which a reward obtained at time ttt from AAA is discounted by ata^tat and one from BBB by btb^tbt. Let

ν~AB(x)=sup⁡τ>0E∑t<τatrA(x(t))E[1−bτ],ν~BA(y)=sup⁡τ>0E∑t<τbtrB(y(t))E[1−aτ].\tilde\nu_{AB}(x) = \sup_{\tau > 0}\frac{\mathbb{E}\sum_{t<\tau} a^t r_A(x(t))}{\mathbb{E}[1 - b^\tau]}, \qquad \tilde\nu_{BA}(y) = \sup_{\tau > 0}\frac{\mathbb{E}\sum_{t<\tau} b^t r_B(y(t))}{\mathbb{E}[1 - a^\tau]}.ν~AB​(x)=τ>0sup​E[1−bτ]E∑t<τ​atrA​(x(t))​,ν~BA​(y)=τ>0sup​E[1−aτ]E∑t<τ​btrB​(y(t))​.

If a policy π\piπ selects, in round ttt with AAA in state xxx and BBB in state yyy, AAA whenever atν~AB(x)>btν~BA(y)a^t \tilde\nu_{AB}(x) > b^t \tilde\nu_{BA}(y)atν~AB​(x)>btν~BA​(y) and BBB whenever atν~AB(x)<btν~BA(y)a^t \tilde\nu_{AB}(x) < b^t \tilde\nu_{BA}(y)atν~AB​(x)<btν~BA​(y) (either when they are equal), then for every initial pair of states (x,y)(x, y)(x,y) 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), AAA paying 0.180.180.18 with a=0.9a = 0.9a=0.9 and BBB paying 111 with b=0.5b = 0.5b=0.5. The states never change, so the printed rule, and any rule that depends only on the states, plays one process forever: payoff 1.81.81.8 for AAA or 222 for BBB. Playing BBB for three rounds and then AAA forever earns 1+0.5+0.25+0.18⋅0.93/0.1=3.0621 + 0.5 + 0.25 + 0.18 \cdot 0.9^3/0.1 = 3.0621+0.5+0.25+0.18⋅0.93/0.1=3.062. The book's proof rescales time so that A∗A^*A∗ and B∗B^*B∗ share a discount factor ccc (AAA's step lasts log⁡cb\log_c blogc​b, with reward (a/b)srA(a/b)^{s} r_A(a/b)srA​ at process time sss). The index of A∗A^*A∗ at process time sss is (a/b)sν~AB(x)ln⁡(1/c)(a/b)^s \tilde\nu_{AB}(x)\ln(1/c)(a/b)sν~AB​(x)ln(1/c), and that of B∗B^*B∗ is (b/a)uν~BA(y)ln⁡(1/c)(b/a)^u \tilde\nu_{BA}(y)\ln(1/c)(b/a)uν~BA​(y)ln(1/c), where ∫0τlog⁡cbcu du=(1−bτ)/ln⁡(1/c)\int_0^{\tau\log_c b} c^u\,du = (1 - b^\tau)/\ln(1/c)∫0τlogc​b​cudu=(1−bτ)/ln(1/c). Comparing them is comparing atν~AB(x)a^t \tilde\nu_{AB}(x)atν~AB​(x) with btν~BA(y)b^t \tilde\nu_{BA}(y)btν~BA​(y) at the global time t=s+ut = s + ut=s+u. The printed denominator E∫0τbtdt=E[1−bτ]/ln⁡(1/b)\mathbb{E}\int_0^\tau b^t dt = \mathbb{E}[1 - b^\tau]/\ln(1/b)E∫0τ​btdt=E[1−bτ]/ln(1/b) replaces the common ln⁡(1/c)\ln(1/c)ln(1/c) by ln⁡(1/b)\ln(1/b)ln(1/b) for one process and ln⁡(1/a)\ln(1/a)ln(1/a) for the other. Nash's generalized-bandit route on p. 66, with Q(A,x)=(b/c)vQ(A, x) = (b/c)^vQ(A,x)=(b/c)v and RA=(a/c)vrAR_A = (a/c)^v r_ARA​=(a/c)vrA​, 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 E∑t<τbt\mathbb{E}\sum_{t<\tau} b^tE∑t<τ​bt are strictly suboptimal in 215 initial states.

Preamble
import Definitions.Def_AllocationIndices_Jobs

open MeasureTheory ProbabilityTheory BanditAlgorithm
Formal statement
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
Source
Gittins, Glazebrook and Weber, Multi-armed Bandit Allocation Indices, 2nd ed., Wiley 2011, doi:10.1002/9780470980033, §3.5.1 pp. 64-65, Theorem 3.4 (Nash), with its proof by a change of time scale; the index denominator and the time weights a^t, b^t are corrected, see the statement
Human review
  • Endorsed by Shuze Chen · Sep 25, 2026

    Confirmed by the moderator at approval.

  • Endorsed by naimengye · Sep 25, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me