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

summary

The gist

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

In short

Coarse Q-learning (CQL) is a reinforcement learning model for bandit problems with stochastically varying menus, using class-level valuations instead of individual alternatives. It shows that this approach generates novel long-run dynamics, including multiple steady states and cycling behaviors, which are impossible in standard Q-learning setups.

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 used across episodes

This episode discusses

The paper

Learning to Choose with Categories: Theory and an Application to Algorithmic Prominence · Read on arXiv

Philippe Jehiel, Aviman Satpathy

Paris School of Economics · University College London

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 >

More episodes

← Home