Learning to Choose with Categories: Theory and an Application to Algorithmic Prominence

arXiv:2412.09321 · econ.TH, cs.GT · Submitted 2024-12-12 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Economics. The day in economics: theory, mechanisms and the evidence beneath them.

Ruth: We're looking at the paper: "Learning to Choose with Categories".

Warren: Here's the gist of the paper. Coarse Q-learning (CQL) is a reinforcement-learning model designed for bandit problems characterized by stochastically varying menus, where alternatives are organized into similarity classes based on an exogenously defined equivalence relation.

Ruth: Learning occurs at this class level, governed by a multinomial logit choice rule over class valuations, and these valuations update via a temporal-difference recursion mirroring Q-learning.

Warren: This coarse aggregation compresses the exponential complexity of alternative-menu pairs into a linear growth in the number of classes, suggesting CQL is a form of stateless Q-learning adopted for cognitive tractability.

Ruth: The continuous-time mean-field dynamics are derived using stochastic approximation, yielding the ODE v dot s = g s(v) - v s, where g s(v) is the expected payoff of class s conditional on choosing s under valuation profile v.

Paper summary: Ruth: To recap, this paper introduces Coarse Q-learning. The thesis is that by partitioning alternatives into similarity classes, we can compress the exponential complexity of choice into a linear growth based on those classes >

Warren: And the learning mechanism involves choosing from those categories using a multinomial logit rule and updating valuations based on realized payoffs, mirroring standard temporal difference updates >

Iris: The central claim is that this coarse aggregation leads to novel long-run dynamics when the payoff sensitivity parameter approaches infinity, which depends on the environment >

Ruth: Yes, because depending on the environment—whether it's two classes or three classes—the model can exhibit multiple stable strict equilibria, a unique globally stable mixed equilibrium with indifference across all classes, or sometimes no stable equilibrium at all >

Warren: The paper also shows that when expected payoffs in singleton menus are very large, this learning pushes valuations toward indifference across multiple similarity classes >

Iris: Conversely, if those singleton expected payoffs are low, the feedback logic supports multiple self-confirming rankings of those similarity classes >

Ruth: These long-run dynamics—indeterminacy, indifference, or instability—are driven by how coarse aggregation interacts with menu-dependent sampling and are not something standard Q-learning can produce >

Warren: The authors use stochastic approximation to get the mean field dynamics, and they rigorously prove structural properties of the solution space as well >

Iris: They establish existence and regularity theorems showing that for any finite number of classes, the correspondence is non-empty and compact on [zero infinity) >

Conclusion: Ruth: So when you look at this work, it’s about how simplifying the decision space—by using categories—creates new types of stable behavior that standard reinforcement learning models simply don't capture >

Warren: The authors are Philippe Jehiel and Aviman Satpathy, and they show that in these coarse settings, you can get complex outcomes like cycling through all possible rankings of classes when there are three classes >

Iris: It’s important to remember that this isn't just a theoretical exercise; it connects the way we perceive things coarsely to the idea of cognitive complexity or choice overload in real-world decision problems >

Ruth: Exactly, and it suggests that modeling choices at a higher level than individual alternatives can actually generate qualitatively different long-run dynamics than what you see in standard Q-learning setups >

Philippe Jehiel, Aviman Satpathy

Paris School of Economics · University College London

econ.TH, cs.GT

Submitted: 2024-12-12

Updated: 2026-11-09

Comments: 45 Main pages + 92 Supplemental Appendix pages

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 92/100

The gist: Coarse Q-learning (CQL) is a reinforcement-learning model designed for bandit problems characterized by stochastically varying menus…

Key concepts

Coarse Q-learning (CQL)
A reinforcement learning model for bandit problems where choices are grouped into similarity classes. Instead of learning the value of every single item, it learns the valuation for each class. This simplifies complex menus into a manageable number of classes, making the learning process more tractable.
Mean-field dynamics
Continuous-time dynamics derived using stochastic approximation to model how valuations evolve over time. The core equation $\dot{v}_s = g_s(v) - v_s$ describes the rate at which a class's valuation changes based on current valuations and expected payoffs.
Steady States (SVE)
The long-run equilibrium points of the learning process. The paper proves that for Coarse Q-learning, these steady states are non-empty and generically finite with odd parity, indicating specific stable or oscillating patterns in how classes are valued over time.

Terminology

Summary

Coarse Q-learning (CQL) is a reinforcement-learning model designed for bandit problems characterized by stochastically varying menus, where alternatives are organized into similarity classes based on an exogenously defined equivalence relation. p. 0 Learning occurs at this class level, governed by a multinomial logit choice rule over class valuations, and these valuations update via a temporal-difference recursion mirroring Q-learning. p. 7 This coarse aggregation compresses the exponential complexity of alternative-menu pairs into a linear growth in the number of classes, suggesting CQL is a form of stateless Q-learning adopted for cognitive tractability. p. 0

The continuous-time mean-field dynamics are derived using stochastic approximation, yielding the ODE v dot s = g s(v) - v s, where g s(v) is the expected payoff of class s conditional on choosing s under valuation profile v. p. 8 The fundamental mechanism driving novel long-run dynamics is the endogeneity of learning: valuations update based on how frequently a category is chosen across different menus. p. 3

The paper establishes that the set of steady states (SVE) under Coarse Q-Learning is non-empty and, generically, finite with odd parity. p. 2 The analysis shows that as the payoff sensitivity parameter approaches infinity, the accumulation points of these steady states select a subset of the Valuation Equilibria (VE) from Jehiel and Samet (2007). p. 2

Key findings detail complex long-run phenomena:

  1. Multiplicity of SVE: In settings with two similarity classes, both multiple steady states and a unique steady state where class valuations are equalized in the high-sensitivity limit (indifference) are demonstrated.

  2. Instability and Cycling: Using a decision problem with three similarity classes, the learning dynamics can exhibit instability, cycling perpetually through all possible rankings of similarity classes.

The long-run dynamics can exhibit indeterminacy (multiple strict rankings), indifference (several categories evaluated as equally attractive), or instability (perpetual fluctuations in revealed patterns of choice). p. 1 When expected payoffs in singleton menus are sufficiently large, the learning pushes valuations toward indifference across multiple similarity classes. p. 3 Conversely, when singleton expected payoffs are low, the feedback logic supports multiple self-confirming rankings of similarity classes. p. 4 Outside these polar regimes, the interaction between coarse perception and menu-dependent sampling can produce endogenous instability. p. 2

The model connects coarse categorization to limited salience and cognitive complexity/choice overload, interpreting CQL as a deliberate form of stateless Q-learning for tractability, while also relating it to Bayesian learning under model misspecification. p. 5 The main contribution is that Coarse Q-learning in the long-run generates novel qualitative phenomena in decision problems with stochastic menus and coarse representation that are otherwise impossible in standard Q-learning setups. p. 1

The mathematical analysis confirms structural properties of the solution space:

  • Existence and Regularity: Theorem 1 establishes that for every finite number of classes, the correspondence V(beta) is non-empty, compact, upper hemicontinuous, and compact-valued on [0, infinity). For generic decision trees and almost every beta, every SVE is regular (I - D vg(v; beta) not equal to 0), meaning the set V(beta) is finite for a. p. 2e. beta.

  • Convergence to VE: Theorem 2 describes the convergence of relative valuation x and mean valuation y under an ODE system, showing that for sufficiently large beta, every SVE lies near a VE. Furthermore, Theorem 6 proves that under Assumption 4. p. 32, every VE must be fully mixed (total indifference among all classes). p. 0

  • Stability: Theorem 6 demonstrates the existence of a unique SVE for large enough z and beta, which is globally asymptotically stable. The proof relies on showing that the eigenvalues of the reduced Jacobian coincide with those of the full system except for a strictly negative eigenvalue, ensuring stability.

  • Strict Pure LSVEs: Theorem 3 proves the existence of a strict pure LSVE under certain conditions, where v infinity is a strict VE satisfying v infinity = g(v infinity). The proof also shows that for every order pi, there exists betaˆ pi(z) < infinity such that for all beta at least betaˆ pi(z), the unique SVE in a neighborhood of v pi(z) is locally asymptotically stable. p. 3

In summary, Coarse Q-learning generates novel qualitative phenomena in decision problems with stochastic menus and coarse representation—phenomena unattainable in standard Q-learning setups. p. 1

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Coarse Inference for Preference Modeling: The improved system can model consumer preference learning by aggregating feedback from alternatives into class-level valuations, allowing it to learn at a higher level of abstraction than individual items. This allows the AI to handle vast and unfamiliar selections by relying on coarse categories based on attributes like region or price range.

  2. Novel Long-Run Phenomenon Detection: The system can identify unique long-run outcomes in decision problems with stochastically varying menus, such as indeterminacy (multiple strict rankings), indifference (evaluating several categories as equally attractive), or instability (perpetual fluctuations in choice patterns).

  3. Robust Equilibrium Selection: The system can select robust valuation equilibria by tracing the high-sensitivity tail of Smooth Valuation Equilibria, which are shown to be unique and locally asymptotically stable for large sensitivity, providing a method for selecting VE even when the set of mixed VE is not isolated.

Related papers