Debate as a training protocol gets its first learning analysis: cooperating debaters can cut mistakes to a constant in some cases
Synopsis
When debate is used as a training protocol, a human judges which of two debaters is right instead of supplying labels. Earlier work analyzed only the game between debaters under a known judge, leaving open how debaters learn the correct function. This work formulates debate as an online learning problem and shows there are cases where adversarial debate cannot learn but cooperative debate needs only a constant number of mistakes, with a new combinatorial dimension characterizing the optimal mistake bound for cooperative debaters in the realizable setting.
Interpretation
The debate protocol is now analyzed as an online learning problem rather than only as a game under a fixed judge. Earlier work assumed the judge was known and analyzed only the game between the two debaters, without addressing how debaters learn the function that judge validates. Each round is written as the environment posing an input, the debaters producing arguments, and the judge returning a binary verdict; the learning goal is for the proposer's predicted label to match the true label, with mistakes counted per round.
The two debaters need not always oppose each other; cooperation can turn some cases from unlearnable into at most a constant number of mistakes. When optimizing the loss for winning the argument, the responder's worst-case loss is the same for every strategy, and the proposer's loss gives no upper bound on prediction mistakes. On a constructed verifier class, adversarial debaters minimizing regret still make prediction mistakes in the worst case, while deterministic cooperative debaters incur at most one prediction mistake.
Learnability for cooperative debaters is exactly characterized by a combinatorial quantity called the debate learning dimension. Standard online learning observes the true labels directly, whereas the learner in debate never sees the true labels and only sees the judge's verdict on the arguments. In the realizable setting, a deterministic learner has a finite mistake bound if and only if it has access to a verifier class supporting the hypothesis class, and the optimal mistake bound equals that verifier class's debate learning dimension.
Perspective
The analysis is confined to the formal debate protocol: a finite certificate space, binary verdicts, fixed debate length, and hypothesis classes induced by verifier classes; results appear as theorems and constructive examples, with no validation on actually trained language models.
The judge is not infallible, and when it returns wrong verdicts in a small number of rounds, the optimal deterministic mistake bound in the realizable setting and the lower bound with misspecified rounds are far apart, so the error rate may never approach the judge's error rate; this sensitivity is proved within the formal model.