#import "../meta/gabri_notes_bk.typ": * #show: gabri_notes.with( instructor: [Max Fishelson (maxfish\@mit.edu)], lec_num: "S6", date: [Fall 2026], title: "Phi-regret minimization", ) #let va = $a$ #let vb = $b$ #let vx = $x$ #let vy = $y$ #let vg = $g$ #let vr = $r$ #let cX = $X$ #let cY = $Y$ #let cR = $R$ #let xhat = $hat(vx)$ #let yhat = $hat(vy)$ #let mU = $upright(U)_1$ We saw in earlier lectures the definition of $Phi$-regret. As we have seen, external regret minimization is a very narrow instantiation of $Phi$-regret minimization---perhaps the smallest sensible instantiation. Then, clearly, the problem of coming up with a regret minimizer for a set $cX$ cannot be harder than the problem of coming up with a $Phi$-regret minimizer for $cX$ for richer sets of transformation functions $Phi$. It might then seem surprising that there exists a construction that reduces $Phi$-regret minimization to regret minimization. We see this general construction in @sec-ggm. First, we start with an example of this principle, whose discovery predates the general construction of @sec-ggm, and which happens to be a special case of it. = Blum-Mansour's swap regret minimization algorithm Let's start by considering the task of constructing a swap regret minimizer for probability simplex $cX = Delta^n$ over $n$ actions $A = {1,...,n}$. As we mentioned when discussing learning, when all players in a normal-form game play according to the strategies generated by such an algorithm, the average product strategy converges to the set of correlated equilibria of the game. The swap regret minimization algorithm of #citet() is a simple and elegant algorithm that minimizes _swap_ regret by starting from multiple copies of an _external_ regret minimizer. Recall that in swap regret minimization, the learner wants to minimize the $Phi$-regret with respect to the set of strategy transformations $Phi$ represented by stochastic matrices $ Phi := {P = (p_1 | dots.c | p_n): p_1, dots.c, p_n in Delta^n}. $ In order to construct a swap regret minimizer for $cX = Delta^n$, we start with $|A|$ copies of an external regret minimizer for $Delta^n$, denoted by $cR_i$. - To compute the `NextStrategy()` of the swap regret minimizer, we first call the `NextStrategy()` of each $cR_i$ to obtain a distribution $p_i^((t)) in Delta^n$. We will then assemble all $p_i^((t))$ into a stochastic matrix $P^((t))$, and will output a fixed point $ x^((t)) = P^((t)) x^((t)) = sum_(i=1)^n x_i^((t)) p_i^((t)) in Delta^n. $ - To compute the `ObserveUtility`$(u^((t)))$ of the swap regret minimizer, we first call the `ObserveUtility` of each $cR_i$ with the linear utility function $ v_i^((t)) := x_i^((t)) u^((t)) $ that is obtained by rescaling $u^((t))$ by the component $x_i^((t))$ of the last-output strategy $x^((t))$. The process can be depicted pictorially as in @fig-bm. #figure(caption: [Blum-Mansour's swap regret minimization algorithm for $Delta^n$.])[ #image("../assets/L08-blum_mansour.svg", width: 100%, alt: "Blum-Mansour construction: an external regret minimizer per action and a fixed-point oracle.") ] We now claim that the algorithm described above is a swap regret minimizer for $Delta^n$. #theorem[ Let $"Reg"_i^((T))$ denote the regret incurred by each external regret minimizer $cR_i$ for $Delta^n$ in the Blum-Mansour construction described above. Then, the swap regret cumulated by the algorithm satisfies: $ "SwapReg"^((T)) = sum_(i=1)^n "Reg"_i^((T)). $ In particular, the swap regret grows sublinearly in $T$ whenever the extenral regret minimizers $cR_i$ guarantee sublinear regret. ] #proof[ By construction, the external regret incurred by each $cR_i$ is #set math.equation(numbering: "(1)") $ "Reg"_i^((T)) = max_(tilde(p)_i in Delta^n) sum_(t=1)^T (v^((t))(tilde(p)_i) - v^((t))\(p_i^((t))\)). $ #set math.equation(numbering: none) Pick any $hat(P) = (hat(p)_1 | ... | hat(p)_n) in Phi$. Then, the swap regret cumulated compared to always transforming strategies according to $hat(P)$ is, by definition, $ &sum_(t=1)^T u^((t))(hat(P) x^((t))) - u^((t)) (x^((t))) \ &#h(1cm)= sum_(t=1)^T u^((t))(hat(P) x^((t))) - u^((t)) ( P^((t)) x^((t)) ) &qquad qquad (x^((t)) = P^((t)) x^((t)))\ &#h(1cm)= sum_(t=1)^T [(sum_(i=1)^n x_i^((t)) u^((t))(hat(p)_i)) - (sum_(i=1)^n x_i^((t)) u^((t))\(p_i^((t))\))] & ("linearity of" u^((t)))\ &#h(1cm)= sum_(t=1)^T (sum_(i=1)^n v_i^((t))(hat(p)_i) - v_i^((t))\(p_i^((t))\)) & ("definition of" v_i^((t)))\ &#h(1cm)= sum_(i=1)^n (sum_(t=1)^T v_i^((t))(hat(p)_i) - v_i^((t))\(p_i^((t))\)) & #h(-15mm) ("switching summation order") \ &#h(1cm)<= sum_(i=1)^n "Reg"_i^((T)). & ("from" (#ref())) $ Taking a maximum over all $hat(P) in Phi$ gives equality: each column $hat(p)_i$ can be chosen independently in $Delta^n$ to attain the corresponding external-regret maximum. This concludes the proof. ] = The general case: Gordon-Greenwald-Marks's reduction Blum-Mansour's swap regret minimization algorithm is a special case of a much more general construction. #citet() show that $Phi$-regret minimization for a strategy set $cX$ can be constructed starting from the following two ingredients: #enum(numbering: "1.")[ an _external_ regret minimization for the set $Phi$; and ][ a _fixed point oracle_ $Phi$, that is, an algorithm that given any $phi.alt in Phi$ outputs a fixed point $phi.alt(vx) = vx in cX$. ] Intuitively, the external regret minimizer for $Phi$ has the role of tracking which transformation $phi.alt$ the decision maker should focus on at each time. The linear utility function $U^((t)) : Phi -> RR$ observed by the external regret minimizer is constructed from the last-output strategy $x^((t))$ and the utility function $u^((t))$ observed at time $t$, according to the formula #set math.equation(numbering: "(1)") $ U^((t))(phi.alt) = u^((t))(phi.alt(x^((t)))), $ #set math.equation(numbering: none) where $vx^((t))$ is the last-output strategy. The final construction is as follows: - Each call to `NextStrategy` first calls $cR$.`NextStrategy` to obtain the next transformation $phi.alt^((t))$. Then, a fixed point $vx^((t)) = phi.alt^((t))(vx^((t))) in cX$ is computed and output. - Each call to `ObserveUtility`$(u^((t)))$ with linear utility function $u^((t))$ constructs the linear utility function $U^((t)): phi.alt |-> u^((t))(phi.alt(vx^((t))))$ given in (@ggm-utility), and passes it to $cR$ via $cR$.`ObserveUtility`$(U^((t)))$. Graphically, we can summarize the process as in the following block diagram. #figure(caption: [Gordon-Greenwald-Marks's reduction from $Phi$-regret minimization to external regret minimization for $Phi$ plus a fixed point oracle for $Phi$.])[ #image("../assets/L08-gordon.svg", width: 100%, alt: "General Phi-regret reduction: utility construction, external regret minimization over transformations, and fixed-point computation.") ] #theorem[#citep()][ The $Phi$-regret $Phi"-Reg"^((T))$ cumulated up to time $T$ by the algorithm we just defined is exactly equal to the (external) cumulative regret $"Reg"_Phi^((T))$ cumulated by $cR$: $ Phi"-Reg"^((T)) = "Reg"_Phi^((T)) qquad forall T = 1, 2, ... . $ Because the regret cumulated by $cR$ grows sublinearly by hypothesis of it being a regret minimizer, then so does the $Phi$-regret of the $Phi$-regret minimization algorithm defined above. ] #proof[ The proof of correctness of the above construction is deceptively simple. Since $cR$ outputs transformations $phi.alt^((1)),phi.alt^((2)),... in Phi$ and receives utilities $phi.alt |-> u^((1))(phi.alt(vx^((1)))), phi.alt |-> u^((2)) (phi.alt (vx^((2))) ), ...$, its cumulative regret $R^((T))$ is by definition $ "Reg"_Phi^((T)) = max_(hat(phi.alt) in Phi) { sum_(t=1)^T (u^((t))(hat(phi.alt) (vx^((t)))) - u^((t))(phi.alt^((t))(vx^((t))))) }. $ Now, since by construction $vx^((t))$ is a fixed point of $phi.alt^((t))$, $phi.alt^((t))(vx^((t))) = vx^((t))$, and therefore we can write $ "Reg"_Phi^((T)) = max_(hat(phi.alt) in Phi) {sum_(t=1)^T (u^((t))(hat(phi.alt) (vx^((t)))) - u^((t))(vx^((t))))}, $ where the right-hand side is exactly the cumulative $Phi$-regret $Phi"-Reg"^((T))$ incurred by $cR_Phi$. ] #lec_bibliography("../meta/refs.bib")