App. B, pp. 17–19 — ET-LRU attains the finite-horizon Bellman optimum from every well-formed belief state
ProvedTailOptCaching.ETLRU.value_etlru_eq_optValuecachingdynamic-programmingoptimal-policyp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be any ET-LRU policy (Definition 1, any tie-break). For every horizon , every starting stage and every well-formed post-decision state , the expected total TEL of the next arrivals under equals the finite-horizon value-to-go function of App. B:
This is the induction of the proof of Theorem 2: at the last arrival every policy is optimal, and if ET-LRU is optimal from arrival on, choosing the myopic minimizer of (8) at arrival loses nothing.
Formalization Note. The state is required to be well formed (in particular ); every state the model reaches is, and planning computations found the claim false from unreachable states with .
Preamble
import Mathlib import Definitions.Def_TailOptCaching_ETLRU_Model open scoped ENNReal
Formal statement
namespace TailOptCaching.ETLRU
theorem value_etlru_eq_optValue (P : Params) (σ : Policy) (hσ : IsETLRU P σ) (M k : ℕ)
(z : State) (hz : WellFormed P z) :
value P σ M k z = optValue P M z := by sorry
end TailOptCaching.ETLRU
Source
Zhang, Li, Moallemi & Peng, Tail-Optimized Caching for LLM Inference, arXiv:2510.15152v1, pp. 17–19, App. B (proof of Theorem 2)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.