Computable universal online learning

Thank you for your review!

Regarding computability, it certainly makes sense to study universal learning under stricter complexity bounds—such as primitive recursiveness or polynomial-time computability. However, the most general notion of effectiveness (i.e., computability) provides a natural starting point for analysis. This approach encompasses all practically meaningful learners. Negative results in this setting are especially informative: if no computable learner exists, then there can be no primitive recursive or polynomial-time learner either. From a presentation standpoint, computability-theoretic proofs are often cleaner and easier to understand than those involving finer-grained bounds like polynomial-time or primitive recursion. At the same time, NeurIPS has already published papers on related formal frameworks (even without any computational constraints) in the recent past (see for instance Z. Lu "When Is Inductive Inference Possible?", NeurIPS 2024). From this perspective, our paper makes a small step closer towards the practical aspects as compared to pure learning theory papers with no computability.

Ad 1. We can think that randomized sampling in LLMs corresponds to decisions made by the Adversary (each path in the tree of random choices is a different possible adversarial behavior). As usual in adversarial setting, we are interested in the worst-case scenario (what is the worst we can see while doing random sampling) as opposed to average case.

Ad 2. Yes, there is a short intuition. In our setting the Adversary is adaptive, which means that they can effectively use a hypothesis outside of the DR or RER class $\mathcal{H}$, even if locally at each round the target hypothesis is consistent with some function from $\mathcal{H}$. To be more precise, the Adversary can use any function from the topological closure \overline \mathcal{H}. A DR class of hypotheses $\mathcal H$ may have a non-computable element $h$ in its closure \overline \mathcal{H}. The intuition is that we can approximate a non-computable object by an infinite sequence of computable ones. To take the LLMs example, any finite sequence of tokens produced by an LLM is computable (even under randomized sampling), but if we let the token generation run indefinitely, we can obtain a sequence that is no longer computable (hence, outside of computable learner's grasp).

Thank you for your response.

While I understand your point about the negative results, in characterizations there also exists the "positive" direction, in which case computability is a low bar.

I'm willing to consider the argument on precedence of computability work (or work without computational constraints) in NeurIPS. However, I had not used the scope of the paper to penalize the submission's rating significantly, so I won't change my score.

Thank you a lot for such a positive review!

Ad. 1 and 2. You are right in both cases. We assume that each hypothesis is a total computable function and indeed, we should have stated in Lemma 5 that each expert is total as well. Thank you for noticing this.

Ad 3. In our argument, the no-regret randomized learner is only assumed to be almost total. This means that the set of random advices on which the algorithm halts is of measure 1 but still it is possible that the algorithm does not halt on some random advice. In such case we cannot always derandomize the algorithm into a computable majority vote. If the algorithm is defined everywhere, on every random advice, we can just enumerate all the random oracles until at some point the computations will stop on exactly measure 1 set of random advices. But if the algorithm is only almost everywhere total, then enumerating random oracles only guarantees that we will keep seeing larger and larger measure, approximating $1$ but possibly never reaching it. Roughly speaking, what can happen is that both label 1 and label 0 will keep having approximately 1/2 of all the measure we have enumerated so far and we will never know what is the value of majority vote. For instance, it could happen that our randomized algorithms halts on random advices of form 01..10 (outputting 0) and 1..10 (outputting 1), in which case we have a tie. But seeing always only a finite set of oracles we cannot distinguish this from the case when for some advice of form 01....1 the output is 1, in which case the majority vote should give 1.

That's why we need this small trick, in which we say that we will care only about the measure that is very close to $1$ (this is our $P'$). On this restricted set of random advices the majority is computable and we then simply note that any additional mistakes we have got this way can be neglected, since we are only interested in the asymptotic property of sublinear regret.

Let us elaborate on the relation between our definitions and the work of Bousquet et al 2021. In the full version of their paper (posted on arxiv) there are at least two learning settings that are called universal learning. You are right that Bousquet et al. 2021 was primarily concerned with studying learning rates under probabilistic sampling. But a crucial technical contribution of their paper - announced in the main paper and developed in the full version - is the notion of ordinal Littlestone dimension and showing that ordinal Littlestone dimension characterizes online learning without uniform mistake bound under Adversarial sampling (compare this to the line 28 of our paper). Bousquet et al 2021 mention this setting on page 535 (the paragraph below Definition 1.7) of the conference paper and refer to the full arxiv version for details, where they call it the "universal variant of online learning" (Section 3.1 on Page 15 of the full arxiv version of their paper). This name was further used by Hanneke et al (ALT 2025). We understand that this may seem somehow confusing and personally, we would prefer to call this setting “non-uniform online learning”. However, in the light of this setting being called “universal learning” and “universal online learning” by other authors (Bousquet et al. 2021, Hanneke et al 2025), we decided to follow the established terminology.

Indeed, our Definition 1 simply repeats the earlier definition of “universally online learnable” as introduced by Bousquet et al (page 15 of the full paper) and then generalized to multiclass learning on page 9 of Hanneke et al 2025. To avoid confusion we will extend the definition with additional explanation: We say that $L$ universally online learns $H$ if for every $H$-realizable sequence $(x_t,y_t)_{t>0}$ there exists $m$ such that for all $n>m$ and every sample $S=(x_1,y_1),(x_2,y_2),...$ we get $L(S,x_n)=y_n$. Again, please note that this definition simply follows the work of previous authors, including that of Bousquet et al.

Similarly, our definition of agnostic learning is adapted from the Definition 6 of Hanneke et al 2025. Please note that we reference this paper in the line 151 when we introduce the agnostic setting. We cannot agree that this definition is incorrect or that it is not clear what setting we formalize, as we give a precise reference to the paper from which we took it. So indeed, for the agnostic learning defined as having sublinear expected regret, it is already known that both realizable and agnostic settings are fully characterized by the ordinal Littlestone dimension, as shown by Hanneke et al 2025. We hope that it is now clear that the base model is already fully understood.

We will disambiguate our citation of Bousquet et al. 2021 to clearly point to the right (adversarial online) setting. We also propose to change “universally learnable” to “universally online learnable” (and similarly “agnostic learning” -> “agnostic universally online learning”) in any occurrence of these notions in the text. This is an easy fix that should help avoid confusion. We will also add a brief comment in the introduction to make it clear that there are two meanings of universal learning in the full version of Bousquet et al. 2021 and that we are concerned with the online one. We humbly note that we have repeated multiple times that we work with an online learning setting. Furthermore, we have provided all relevant definitions in the text, which should clear any confusion. We believe that our presentation, together with the suggested improvements, is of sufficient mathematical rigour, similar to that usually encountered in learning theory papers.

The expression “where data distributions may shift.” refers to the fact that in the universal online learning setting the Adversary is adaptive and can change the target function. We will remove this sentence to avoid unnecessary confusion. Similarly, “multi-armed bandit” are mentioned simply as an example of many formal models studied in learning theory.

Let us elaborate on the relation between our definitions and the work of Bousquet et al 2021. In the full version of their paper (posted on arxiv) there are at least two learning settings that are called universal learning. You are right that Bousquet et al. 2021 was primarily concerned with studying learning rates under probabilistic sampling. But a crucial technical contribution of their paper - announced in the main paper and developed in the full version - is the notion of ordinal Littlestone dimension and showing that ordinal Littlestone dimension characterizes online learning without uniform mistake bound under Adversarial sampling (compare this to the line 28 of our paper). Bousquet et al 2021 mention this setting on page 535 (the paragraph below Definition 1.7) of the conference paper and refer to the full arxiv version for details, where they call it the "universal variant of online learning" (Section 3.1 on Page 15 of the full arxiv version of their paper). This name was further used by Hanneke et al (ALT 2025). We understand that this may seem somehow confusing and personally, we would prefer to call this setting “non-uniform online learning”. However, in the light of this setting being called “universal learning” and “universal online learning” by other authors (Bousquet et al. 2021, Hanneke et al 2025), we decided to follow the established terminology.

Indeed, our Definition 1 simply repeats the earlier definition of “universally online learnable” as introduced by Bousquet et al (page 15 of the full paper) and then generalized to multiclass learning on page 9 of Hanneke et al 2025. To avoid confusion we will rewrite lines 88-92, highlight the main difference between uniform and non-uniform set-ups and extend the definition with additional symbolic explanation: We say that $L$ universally online learns $H$ if for every $H$-realizable sequence $(x_t,y_t)_{t>0}$ there exists $m$ such that for all $n>m$ and every sample $S=(x_1,y_1),(x_2,y_2),...$ we get $L(S,x_n)=y_n$.

Similarly, our definition of agnostic learning is adapted from the Definition 6 of Hanneke et al 2025. Please note that we reference this paper in the line 151 when we introduce the agnostic setting. So indeed, for the agnostic learning defined as having sublinear expected regret, it is already known that both realizable and agnostic settings are fully characterized by the ordinal Littlestone dimension, as shown by Hanneke et al 2025 (Theorem 3 there).

We will disambiguate our citation of Bousquet et al. 2021 to clearly point to the right (adversarial online) setting. We also propose to change “universally learnable” to “universally online learnable” (and similarly “agnostic learning” -> “agnostic universally online learning”) in any occurrence of these notions in the text. This is an easy fix that should help avoid confusion. We will also add a brief comment in the introduction to make it clear that there are two meanings of universal learning in the full version of Bousquet et al. 2021 and that we are concerned with the online one. We humbly note that we have repeated multiple times that we work with an online learning setting. Furthermore, we have provided all relevant definitions in the text, which should clear any confusion. We believe that our presentation, together with the suggested improvements, is of sufficient mathematical rigour, similar to that usually encountered in learning theory papers.

Regarding flexibility of the Adversary. In the uniform case, it doesn’t matter if the Adversary can change the target function. If the Littlestone dimension is finite, then we can achieve uniform mistake bound even if the Adversary is adaptive and if the Littlestone dimension is not finite, Adversary does not need to be adaptive to force $k$ mistakes for arbitrary $k$. Perhaps for this reason, many authors choose to say instead that the target function is fixed in advance (for instance, see the standard textbook by Shai Shalev-Shwartz and Shai Ben-David). In fact, this is how the setting was originally defined in Littlestone 1998. The flexibility only matters when we drop the requirement of uniformity. This is why we highlighted this aspect in our presentation.

Regarding computable learners. In online learning a learner outputs a prediction on a point, not a whole function. The definition 8 from Agarwal et al. 2023 is a definition of computable learner in cPAC setting, not in online learning. Our definition of a learner (see line 140) follows that used by previous authors, both in standard online learning and in its computable version e.g. Hasrati and Ben-David 2023 or Delle Rose et al 2025. A computable learner is just a function $f$ such that $f$ is a learner and $f$ is computable. We use “computable” in the standard sense. The only subtle point in our setting is concerned with learner being a partial or total computable function but this distinction is discussed in detail in the paper.

We will add the reference to the Lines 127-129. This reference is not Delle Rose et al 2025. Please note that the correct references were already given when the claim first appeared in line 50.

Regarding proper learners. First of all, let us say that for the universal online learning, there is no established notion of 'proper learning' yet. In other learning settings, “proper” usually means 'predicting always according to some function from the class'. In the non-uniform online learning, this notion is too strong, since the Adversary can effectively use a function that is not in the class (but rather in its topological closure). Therefore, to be able to say something non-trivial, we decided to define 'proper universal online learning' as 'predicting always according to some realizable function". The Reviewer also asked about proper vs improper learning in cPAC setting. This scenario differs in many ways from our case. Proper cPAC learning is problematic in the agnostic case, when we cannot guarantee a computable Empirical Risk Minimizer (ERM). In computable universal online learning, proper is problematic already in the realizable case. In the realizable cPAC, every $RER$ class of finite VC dimension is properly cPAC learnable in the realizable case (see Agarwal et al 2020). This is because in the realizable setting, any $RER$ class has a computable ERM. This can be contrasted with the universal online learning setting, where even a computable ERM is not always enough to construct a computable learner. This observation (Proposition 1) is one of the main contributions of our paper.