The Optimizers We Build
Humans do not optimize. They do not have computers in their brains that help with decision making. But hang on. We use computers all day long to help augment our abilities. In fact, corporations everywhere are using machine learning to turn problems that used to be solved by humans are not being solved by machines. Under the hood of every ML algorithm is some sort of optimization, either reducing the error from predictions or in the case of decision (reinforcement learning) bots solving dynamic problems.
So what does this all mean? Imagine I run a marketplace. Third parties sell on it and set their own prices, using whatever technology they like. As the owner, I want to know how participants will respond if I change the rules. This is the classic structural econometric question: how do agents in a system adapt to a new environment when I allow them to re-optimize?
The last part of this question is crucial and so it makes sense to briefly think about this with a simple example. You run security at a bank. You notice that you have security guards on payroll but there are no bank robberies. So, given this pattern, you decide to fire all your security guards. From one day to the next you are being robbed left right and centre. This example seems ridiculous. And it is. But it captures the key problems with building decisions on existing statistical patterns and ignoring re-optimization. Economists have been worrying about these system responses for decades.
So back to our setting. I want to change the rules of a marketplace but I know re-optimization is going to happen. But here is one more wrinkle. Take two firms in this marketplace. They delegate pricing to agents. Each firm hands its agent a reward, some payoff it cares about, and lets the agent optimize against it. The agent sets a price, the market responds, and the agent logs the reward. Prices are set in alternating moves, which captures the fact that firms' decision epochs need not line up. The agents learn by a fancy sounding algorithm. I am thinking of entropy-regularized Q-learning, a pretty popular choice.
And I know these bots are going to re-optimize. So I can’t just look at the pricing behavior from before the rule change and make predictions. However, economics has been working away in the ivory tower to figure out how to reverse engineer the underlying utility functions humans use when making decisions. These utility functions represent the inherent preference structure of the human. This reverse engineering only works because we assume that humans are rational optimizers. But we know that’s a tricky assumption. However, in the case of synthetic agents we are back in business because we know that they optimize.
Now, the owner can reverse-engineer something useful from the behavior. First you can measure directly the strategies the bots use. And it is possible to use the strategies and the representation of the optimization problem to invert out the reward/utility function the bot was given. This reward function can then be used for each bot as an input into simulation where can test different marketplace rules to see responses.
Let me just briefly show symbolically how this can be done. Let me say I have enough data on binary choices that I can tell you what the probability is that someone picks from two options {A,B}. Now assume that this choice reveals something about preferences, i.e. if you see someone pick A we say that they prefer A to B. Take that one more step further, we can say that
U(A)>U(B)
where U(.) is the magic utility function. Let’s say there is one little bit of uncertainty around the utility. Each choice gets its own little random variable “shock”. So now:
Pr(A chosen)=Pr(U(A)+eA>U(B)+eB)
where eA and eB are the shocks that have some probability distribution. With some specific assumptions I can end up with this:
Pr(A chosen) = exp(U(A))[exp(U(A))+exp(U(B))]^(-1)
And so what? Well look at this:
Pr(A chosen)/Pr(B chosen) = exp(U(A))/exp(U(B))
Take logs and I get:
ln [Pr(A chosen)/Pr(B chosen)] = U(A)-U(B)
I can directly measure the utility differences between two options from the data, because the left hand side is just the probability of choosing A or B. So, now we have uncovered a latent utility function that represents the inherent rewards from each choice. Now humans don’t always optimize. That fact is embodied in the notion that a choice A over B implies
U(A)+eA>U(B)+eB
However, with RL bots that worries is no longer relevant. The bots do optimize and they use techniques where actions are chosen probabilistically. We can then apply the exact inversion logic shown above to our RL-agent setting. It turns out a lot of econometric techniques can be adapted to synthetic agents. The same logic as above can be applied to the choices of the bots in the marketplace. We require some supporting assumptions and structure we can direclty get reward function. With those in hand we can then simulate different environments and be robust to re-optimization. We can do this because we have those inherent payoff functions for the bots.
I ran a simulation to show that this is possible with Q learning agents in the pricing game I setup above. In the setup bots move alternately and set prices knowing what the other bot price is. The bots want to maximize the discounted stream of rewards. The strategies they find are shown below.
The next step is to use the strategies we can estimate from the data of this marketplace to invert the reward function out. There is one wrinkle. In the Q learning algorithm there is a temperature that determines learning. That parameter cannot be retrieved by our inversion. So we have to sweep all values of that temperature and then we can run simulations for every single temperature value to see the full picture. We then test to experiments: a profit tax and a per unit tax.
I do not want to overstate what I am proposing here. The point is that many RL agents can be understood from their most primitive input: the reward function. ANd sometimes we can invert out exactly the reward function the agent is using.
References
I make a lot of claims in the text. For the curious, here is a slightly more detailed discussion of the literature. The (hidden) claim this whole post rests on is that reinforcement learning agent's choice rule and the econometrician's estimator are the same object. The formal statement that Maximum Causal Entropy IRL from machine learning and the dynamic discrete choice estimators from economics (the Nested Fixed Point algorithm, the Conditional Choice Probability method, and the Nested Pseudo-Likelihood algorithm) all belong to a single class of optimization problems, sharing a common objective, policy, and gradient, is due to:
Groeger, J., with N. Sanghvi, S. Usami, M. Sharma, and K. Kitani (2021). "Inverse Reinforcement Learning with Explicit Policy Estimates." Proceedings of the AAAI Conference on Artificial Intelligence, 35(11), 9472–9480. https://doi.org/10.1609/aaai.v35i11.17141
That paper highlights that popular choices for Q-learning algorithms coincide with the standard setup for dynamic discrete choice models. Once the estimators are known to coincide, we can lean on the economics results on identification, that is, whether it is possible to map from observed data back to the hidden parameters. That in turn tells us which counterfactuals (experiments that let the agents re-optimize) can be run under minimal assumptions, and which ones force the investigator to compromise and report only bounds.
The supporting literature it connects sits on both sides of that bridge.
On the economics side, the dynamic discrete choice tradition: Rust (1987) on the nested fixed point and the logit-shock formulation; Hotz and Miller (1993) on inverting choice probabilities; Magnac and Thesmar (2002) on what is and is not identified, and the necessity of normalizing the shock scale; Pesendorfer and Schmidt-Dengler (2008) on asymptotic least squares; and Kalouptsidi, Scott, and Souza-Rodrigues (2021) on which counterfactuals are identified when the payoff is not.
On the machine learning side, the entropy-regularized reinforcement learning tradition: Ziebart (2010) on maximum causal entropy IRL; Haarnoja et al. (2017) on soft Q-learning; and Geist, Scherrer, and Pietquin (2019) on regularized Markov decision processes.
For the eagle-eyed there is still one loose end worth addressing: humans keep tweaking the reward function over time as results from an agent come in, so the reward functions themselves keep moving. There is no clever fix for this other than running a constant estimation loop coupled with some form of outlier detection.
