Example 7.4.1 — the improvement bound of Lemma 7.2.2 is tight for all α and γ
ProvedSampleComplexityRL.CPI.example_tightdynamic-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1reinforcement-learning
Consider the two-state MDP with states and actions at each state. At , action is a self transition with reward and action moves to with reward . At both actions are self transitions, with and . The reset distribution is the point mass at . Let be the deterministic policy , the deterministic policy , and . Values are normalized and , .
Then:
- ;
- , , and ;
- the future advantage is and ;
- and
- consequently the improvement equals the lower bound of Lemma 7.2.2:
The example shows that the conservative-update bound cannot be improved uniformly in and , which is why CPI's step size is set from the worst case.
Formalization Note The thesis writes the state as "1" in its last two displays; here it is . The actions are the constructors one, two, and are indicator policies.
Preamble
import Mathlib import Definitions.Def_FoundationsML_ReinforcementLearning_IsTransitionKernel import Definitions.Def_FoundationsML_ReinforcementLearning_IsPolicy import Definitions.Def_ApproxOptRL_Shared_Model import Definitions.Def_ApproxOptRL_CPI_PolicyAdvantage import Definitions.Def_SampleComplexityRL_CPI_ExactCPI open ApproxOptRL.Shared ApproxOptRL.CPI FoundationsML.ReinforcementLearning
Formal statement
namespace SampleComplexityRL.CPI
/-- **Example 7.4.1** (Kakade 2003, p. 94): the improvement bound of Lemma 7.2.2 is tight for
all `α ∈ [0, 1]` and `γ ∈ [0, 1)`. Two states `i, j`, two actions `1, 2` (`one`, `two`),
reset distribution the point mass at `i`, `π` = always action `1`, `π'` = always action `2`,
`π_new = (1 − α)π + απ'`. Then `d_{π,i}(i) = 1`, `A_π(i,2) = (1−γ)/2`, `A_π(j,2) = −(1−γ)/2`,
the advantages of the actions taken by `π` are `0`, `𝔸_π(i, π') = (1−γ)/2`,
`ε_∞ = (1−γ)/2`, `V_π(i) = 1/2`, `V_{π_new}(i) = 1/2 + α/2 − γα²/(1 − γ(1 − α))`, and
`V_{π_new}(i) − V_π(i)` equals the right-hand side of Lemma 7.2.2. -/
theorem example_tight (γ α : ℝ) (hγ0 : 0 ≤ γ) (hγ1 : γ < 1) (hα0 : 0 ≤ α) (hα1 : α ≤ 1) :
let μ : ExState → ℝ := pointMass ExState.i
let πnew : ExState → ExAction → ℝ := mixPolicy α exPi exPi'
let εinf : ℝ := Finset.univ.sup' Finset.univ_nonempty
(fun s => |∑ a, exPi' s a * advantage exP exR γ exPi s a|)
futureStateDist exP γ exPi μ ExState.i = 1 ∧
advantage exP exR γ exPi ExState.i ExAction.two = (1 - γ) / 2 ∧
advantage exP exR γ exPi ExState.j ExAction.two = -((1 - γ) / 2) ∧
advantage exP exR γ exPi ExState.i ExAction.one = 0 ∧
advantage exP exR γ exPi ExState.j ExAction.one = 0 ∧
policyAdvantage exP exR γ exPi μ exPi' = (1 - γ) / 2 ∧
εinf = (1 - γ) / 2 ∧
value exP exR γ exPi ExState.i = 1 / 2 ∧
value exP exR γ πnew ExState.i = 1 / 2 + α / 2 - γ * α ^ 2 / (1 - γ * (1 - α)) ∧
value exP exR γ πnew ExState.i - value exP exR γ exPi ExState.i =
α / (1 - γ) * (policyAdvantage exP exR γ exPi μ exPi' -
2 * γ * α / (1 - γ * (1 - α)) * εinf) := by sorry
end SampleComplexityRL.CPI
Source
Kakade, On the Sample Complexity of Reinforcement Learning, PhD thesis, University College London, 2003, p. 94, Example 7.4.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.