Minimax regret under an affine change of the loss matrix
ProvedBanditAlgorithm.pm_minimax_regret_of_affine_lossMinimax regret in partial monitoring is unchanged by shifting the loss matrix along outcomes, and scales linearly when the losses are rescaled.
Let and be partial monitoring games with the same feedback matrix, whose loss matrices are related by
where the shift may depend on the outcome but not on the action . Then for every horizon ,
The reason is that regret is defined through loss differences : the shift appears in both terms and cancels identically, while factors out of the sum, the integral, the supremum over comparator actions, the supremum over outcome sequences and the infimum over policies.
This is the normalisation step that lets results proved for games with losses in be applied to a game with an arbitrary real loss matrix: since a loss matrix is finite, it can always be brought into by such an affine map, and any constants in the conclusion simply rescale.
Formalization Note The interaction measure depends on the game only through the feedback matrix , never through — the learner observes signals, not losses — so the two games induce literally the same law over histories, which is what makes the comparison exact rather than merely asymptotic. Nonnegativity of is needed: for the suprema and infima would exchange.
import Definitions.Def_PartialMonitoringGame open MeasureTheory ProbabilityTheory
theorem BanditAlgorithm.pm_minimax_regret_of_affine_loss {k d : ℕ} {𝕊 : Type*}
[Fintype 𝕊] [MeasurableSpace 𝕊]
(G G' : PartialMonitoringGame k d 𝕊)
(lam : ℝ) (hlam : 0 ≤ lam) (c : Fin d → ℝ)
(hL : ∀ a i, G'.L a i = lam * G.L a i + c i) (hΦ : G'.Φ = G.Φ) (n : ℕ) :
pmMinimaxRegret G' n = lam * pmMinimaxRegret G n := by
sorry