In traditional online learning and multi-armed bandit frameworks, algorithms rely on precise numerical feedback. An agent chooses an action and receives a cardinal reward (e.g., a utility score of $0.8$). In real-world applications like search engines, recommendation systems, and human-in-the-loop reinforcement learning, obtaining exact numerical values is often impossible. Instead, we must rely on ranking feedback—ordinal observations indicating that "Item A is preferred to Item B," or implicit signals like a user clicking on the top-ranked document.
While ranking feedback is cleaner and easier to collect, a growing body of research reveals a fundamental theoretical bottleneck: in many standard online settings, achieving sublinear regret is mathematically impossible when feedback is restricted to rankings.
To understand why this hardness arises, we must look at how ordinal feedback strips away the critical geometric information that learning algorithms need to converge.
The Scale Blindness of Ordinal Feedback
The primary reason ranking feedback fails in adversarial or non-stochastic environments is that it obscures the magnitude of performance differences.
Consider an online learning agent trying to choose the best action. In a standard setup, the agent uses the numerical gaps between action rewards to penalize poorly performing choices and converge toward the optimal one. However, as shown by Davide Maran et al. in Bandits with Ranking Feedback, an adversary can exploit ranking-only feedback by manipulating hidden numerical rewards to maintain a completely static ranking. Because the relative order of the options never changes, the feedback signal becomes entirely uninformative regarding the actual cumulative rewards. The learner cannot determine whether the gap between the top option and the runner-up is massive or negligible, preventing the achievement of sublinear regret.
This limitation is further generalized to online equilibrium computation by Mingyang Liu et al. in Online Learning with Ranking Feedback and An Application to Equilibrium Computation and Online Learning and Equilibrium Computation with Ranking Feedback. The authors demonstrate that when feedback is restricted to instantaneous rankings within a purely adversarial environment, the lack of historical context and numerical scale prevents the learner from effectively countering malicious or highly volatile utility changes over time.
The Sparsity of Top-1 Feedback
The impossibility of learning from rankings becomes even more pronounced in Online Learning to Rank (OL2R), where an agent displays an ordered list of items and only observes user interactions at the very top of the list.
[ Displayed List ] [ User Feedback ]
1. Document A <---> Clicked / Approved (Visible)
2. Document B <---> Ignored (Hidden)
3. Document C <---> Ignored (Hidden)
In Online Learning to Rank with Feedback at the Top, Ambuj Tewari et al. prove that if feedback is restricted strictly to the single top-ranked item ($k=1$), achieving sublinear regret is impossible for complex, list-wide ranking metrics like Normalized Discounted Cumulative Gain (NDCG).
Why does this happen? High-quality ranking metrics like NDCG, Average Precision (AP), and Area Under the Curve (AUC) are calibrated to evaluate the precision of the entire list. As Sougata Chaudhuri et al. explain in Online Learning to Rank with Top-k Feedback, top-1 feedback is simply too sparse to differentiate between distinct adversarial relevance patterns across the rest of the unobserved list. If the learner only knows that the first item was successful, it remains completely blind to whether the items placed in positions 2 through 10 were highly relevant or completely useless, making list-wide optimization an impossible task.
Even Stochastic Environments Suffer
One might assume that these impossibility results are merely artifacts of malicious adversaries. However, the hardness of ranking feedback extends even to benign, stochastic environments.
In a standard stochastic multi-armed bandit, an agent can achieve logarithmic regret because it can rapidly estimate the expected numerical reward of each arm. But when feedback is limited to the ranking of the arms' cumulative empirical means, Davide Maran et al. prove that logarithmic regret is mathematically unachievable. Without numerical rewards, the learner cannot gauge the proximity of different options' performances. To avoid being permanently misled by early random fluctuations (random walk trajectories), the agent is forced to engage in aggressive, superlogarithmic exploration, fundamentally slowing down the learning rate.
Circumventing the Impossibility
Because pure ranking feedback imposes such rigid theoretical limits, recent literature focuses on identifying the exact conditions required to break through these impossibility barriers. Two primary levers have emerged:
- Expanding the Feedback Window ($k > 1$): Sougata Chaudhuri et al. demonstrate that while top-1 feedback triggers impossibility results, allowing the feedback set to be even slightly larger than the top item ($1 < k < m$) provides enough structural information to achieve near-optimal regret bounds for metrics like NDCG.
- Leveraging Historical Memory: Rather than relying on instantaneous, round-by-round rankings, Mingyang Liu et al. show that if the learning framework incorporates feedback based on historical averages, or if the environment exhibits structural stability, sublinear regret and game-theoretic equilibria computation suddenly become viable.
Key Foundational Work
Online Learning to Rank with Feedback at the Top. (2016) — contributed 5 concept elements to this direction.
Online Learning to Rank with Top-k Feedback. (2017) — contributed 3 concept elements to this direction.