Self-aware feedback graph
DefinitionFirstOrderFG_Supplement_SelfAwarebandit-algorithmsgraph-theorymachine-learningp2o-gran-per-chapterp2o-plan-paperp2o-v1
A directed feedback graph is self-aware when every arm has a self-loop. Thus playing any arm always reveals that arm's own loss, and the self-loop vertex set is the whole arm set.
This is the graph regime of Algorithms 1 and 3 and Theorems 3.2 and A.2.
Definition code
import Mathlib
set_option autoImplicit false
namespace FirstOrderFG.Supplement
/-- **A self-aware feedback graph.** Zhang–Zhang–Luo–Mineiro,
*Near-Optimal First-Order Regret for Bandits with Feedback Graphs*, arXiv:2610.40861,
§2, p.3: `G` is self-aware when every vertex has a self-loop, equivalently `V_self = V`.
**Formalization Note.** `E i j` means that playing `i` reveals the loss of `j`. -/
def SelfAware {K : ℕ} (E : Fin K → Fin K → Prop) : Prop :=
∀ i, E i i
end FirstOrderFG.Supplement
Source
Zhang–Zhang–Luo–Mineiro, Near-Optimal First-Order Regret for Bandits with Feedback Graphs, arXiv:2610.40861, §2, p.3