The Thermometry Problem: Online Learning with Ranking Feedback

Introduction

Before the Celsius scale, scientists practiced ordinal thermometry. They could reliably determine that mercury in vessel A expanded more than in vessel B, establishing a "hotter than" relationship without ever knowing if the temperature difference was one degree or one hundred. This ordinal approach provided clear local comparisons but obscured the cardinal information necessary for heat conservation calculations or absolute measurements. The information loss, as it turned out, mattered enormously for what physics could compute.

This historical analogy captures the central tension in a recent paper by Liu, Chen, Fan, Farina, Ozdaglar, and Zhang, titled Online Learning and Equilibrium Computation with Ranking Feedback, presented at ICLR 2026. The authors investigate online learning in adversarial environments where the learner does not receive numeric utility feedback, but instead observes only a ranking over proposed actions. This setting is increasingly relevant for human-in-the-loop applications such as reinforcement learning from human feedback (RLHF), recommendation systems, and matching platforms, where humans find it easier to compare items than to provide calibrated numerical scores. The fundamental question is whether sublinear regret remains achievable when we strip away cardinal utilities and retain only ordinal comparisons.

The Impossibility of Snapshot Comparisons

The paper distinguishes between two ranking mechanisms. The first, instantaneous utility ranking (InstUtil Rank), generates rankings based solely on the utility vector at the current timestep. At each round, the learner proposes a set of actions and receives their ordering according to the immediate rewards. Intuitively, this feedback seems impoverished, and the authors confirm this suspicion with a strong negative result: sublinear regret is impossible in general under InstUtil Rank, even in the full information setting where the learner observes the complete ranking over all actions.

The reason for this lower bound of Ω(T) regret lies in the fundamental ambiguity of rankings. An adversarial environment can construct utility sequences where the ranking remains constant while the underlying utility differences oscillate wildly. Because the learner observes only the order, not the magnitude or direction of utility changes, it cannot distinguish between a scenario where action 1 marginally beats action 2 and one where action 1 is vastly superior. The ranking provides no gradient information. Without memory of past performance or smoothness in the utility evolution, the learner is effectively blind to the adversary's movements, forced to accumulate linear regret as it fails to track the best action in hindsight. This result formalizes the intuition that instantaneous comparisons, much like isolated thermoscopic observations, cannot anchor a learning process in nonstationary environments.

Memory, Smoothness, and the Path to Learnability

If instantaneous rankings fail, the paper proposes that time-average utility ranking (AvgUtil Rank) may restore learnability. In this model, the ranking at timestep t is induced not by the current utility vector, but by the cumulative average of utilities observed up to t. This captures settings with long-lived agents who possess memory, such as returning customers on a recommendation platform who rank options based on their cumulative satisfaction.

However, even with AvgUtil Rank, sublinear regret remains unattainable without additional structure. The authors analyze the ranking generation through the Plackett-Luce model, a standard choice model where the probability of a ranking decreases exponentially with the temperature parameter τ. When τ is small, meaning the ranking is highly deterministic and closely follows the utility order, the feedback becomes too rigid. The paper establishes that for sufficiently small τ, the regret remains linear up to logarithmic factors, as the deterministic ranking again masks the underlying utility magnitudes.

The key to positive results lies in imposing a sublinear total variation assumption on the utility sequence. This condition requires that the cumulative change in utilities over T rounds grows sublinearly (o(T)), effectively assuming that the environment, while possibly adversarial, does not oscillate too rapidly. Under this assumption, the authors develop novel algorithms that achieve sublinear regret. Notably, for the full information AvgUtil Rank setting with constant temperature τ, the variation assumption can be removed entirely; sublinear regret is guaranteed regardless of utility variation. This suggests that the combination of historical averaging and sufficient randomization in the ranking model (large enough τ) provides enough signal for the learner to approximate the utility landscape and converge to no-regret behavior.

Game Theory, Privacy, and Practical Implications

Beyond single-agent learning, the paper extends its analysis to normal-form games, demonstrating that when all players employ the proposed algorithms, the time-average play converges to an approximate coarse correlated equilibrium (CCE). This is significant because it shows that equilibria can be computed without players ever revealing their exact payoffs. In applications such as online dating or ride-sharing platforms, where users rank potential matches but keep their exact valuation functions private, this result guarantees that the platform can still guide the system toward a stable outcome while respecting informational privacy.

From a broader perspective, this work highlights a critical distinction between cardinal and ordinal utility that transcends its economic origins. In RLHF, for instance, human annotators provide preference rankings over model outputs, which are typically modeled using the Bradley-Terry or Plackett-Luce specifications. The paper's analysis suggests that the "temperature" of these comparisons, how noisy or deterministic they are, fundamentally determines whether fine-tuning can succeed in adversarial or nonstationary contexts. If human preferences are too deterministic (low effective τ), the learning agent may face the same impossibility results, requiring either smoother utility landscapes or explicit regularization in the preference model to ensure learnability.

Conclusion

The thermometry analogy ultimately proves apt. Just as the development of thermodynamics required the calibration of temperature scales, online learning requires cardinal information to navigate adversarial landscapes efficiently. The work of Liu et al. rigorously quantifies this cost: instantaneous rankings provide insufficient signal, while time-average rankings, under appropriate smoothness conditions or with sufficient stochasticity, can restore sublinear regret and equilibrium computation.

Looking forward, several questions remain open. The paper assumes complete rankings over all actions; what happens with partial rankings or top-k feedback? How do these results extend to contextual bandits or settings with infinite action spaces? As machine learning systems increasingly rely on human ordinal feedback, understanding the computational limits of comparison-based learning becomes not merely a theoretical exercise, but a practical necessity for designing robust, privacy-preserving, and human-compatible algorithms.