Sample policies and the full-information adversarial optimum
DefinitionSampleCRS_AlmostGreedy_Supplement_sampleModelA sample policy sees all Bernoulli sample rows before it begins and returns an online kernel. The same policy is used for every hidden vector . The sample array, online activations and subsequent kernel random choices are independent in the experiment. Each sample row has the published activation law, and the sample-array weight is
Sample acceptance averages the actual kernel law over this array. With , the empty product is one.
For capacity , let be the supremum of attainable by full-information online schemes uniformly over every finite and every admissible vector of mass :
Here full-information policies may depend on ; sample policies cannot. This bounded, nonempty supremum defines the adversarial optimum independently of any impossibility conclusion or ODE characterization.
import Mathlib
import Definitions.Def_SampleCRS_AlmostGreedy_Supplement_onlineKernel
namespace SampleCRS.AlmostGreedy.Supplement
/-- All samples are visible before the run. There is no hidden `p` argument. -/
abbrev SamplePolicy (n m : ℕ) := (Fin m → Fin n → Bool) → OnlineKernel n
noncomputable def sampleWeight {n m : ℕ} (p : Fin n → ℝ)
(Y : Fin m → Fin n → Bool) : ℝ :=
∏ s, activationWeight p (Y s)
noncomputable def sampleAccept {n m : ℕ} (k : ℕ) (π : SamplePolicy n m)
(p : Fin n → ℝ) (i : Fin n) : ℝ :=
∑ Y, sampleWeight p Y * policyAccept k (π Y) p i
/-- Full-information adversarial balance: the policy may be chosen after seeing p.
Relabelling a fixed, even advance-known, order to `0,…,n-1` loses no information. -/
def AdvAttainable (k : ℕ) (c : ℝ) : Prop :=
c ∈ Set.Icc (0 : ℝ) 1 ∧
∀ (n : ℕ) (p : Fin n → ℝ), ValidProb p → (∑ i, p i) = (k : ℝ) →
∃ π : OnlineKernel n, BalancedInstance k c π p
/-- The operational known-p adversarial optimum, not the random-order constant.
The defining set is bounded by 1; 0 is attainable by rejecting every arrival. -/
noncomputable def gammaAdv (k : ℕ) : ℝ := sSup {c : ℝ | AdvAttainable k c}
end SampleCRS.AlmostGreedy.Supplement