The previous reduction of linear feasibility to online learning would take the average of super-optimal solutions, so we would end up with a super-optimal \(\varepsilon\)-feasible solution, i.e., an \(\varepsilon\)-feasible solution to the optimisation problem!
We don't even know what the optimal solution value is, so it's hard to implement the optimisation oracle for \(X\). There's another trick that can help us: we don't need an optimisation oracle to make the reduction work, we only need a feasibility oracle. As long as we always find one \(x \in X\) such that \( p^\top A x \leq p^\top b\), the expected payoff will be non-positive, and the reduction works—and, if there is no such solution, the problem is infeasible.
We can find such a solution by solving to optimality the surrogate relaxation subproblem