MDPs, poker, and a $10,000 MRI

I spent today ideating startups with my friend. The idea we kept coming back to was finding failures in agents. Not building eval suites for them, which is a different thing, but figuring out the actual reason an agent fails. You break the agent on purpose and then work backwards to why.

The more we talked about it the more it turned into a causality problem. To know why an agent failed you have to know what caused it, and that is not the same as noticing what correlated with it. Everything we came up with kept landing back there.

Which is when it clicked that we were describing the research we are already doing. Causal observability, structural causal models, the whole thing. We started out just wanting to build something, and then realized the thing we wanted to build was sitting inside the paper we had been reading.

So my friend and I went back to the paper properly. And the paper sits on top of a stack of things I had only half looked at, so I spent the rest of the day going down it.

Chains, then decisions

At the bottom is the Markov property. States, and the chance of moving between them:

$$P(s_{t+1} \mid s_t, s_{t-1}, \dots, s_0) = P(s_{t+1} \mid s_t)$$

The future depends only on where you are now, not on how you got there. That is a Markov chain, and nothing in it decides anything. I had been using "Markov chain" and "Markov decision process" as if they were the same thing, which they are not, and the difference turns out to be the part I care about.

A decision process keeps the property and adds the pieces that make something act:

$$\mathcal{M} = (S, A, P, R, \gamma)$$

Actions, a reward, a transition function that now depends on what you did, and a discount for how much you care about later. That is the version that matters for reinforcement learning, and it is closer to causality, because something is choosing and the choice changes what comes next.

Then the value of being somewhere, which is defined in terms of itself:

$$V^*(s) = \max_a \Big[ R(s,a) + \gamma \sum_{s'} P(s' \mid s, a)\, V^*(s') \Big]$$

The best you can do now, plus the discounted value of wherever that puts you. It refers to itself, which is what lets it run forever. I am still working through that part.

The chain version has a good origin story. Markov took the first 20,000 characters of Pushkin's Eugene Onegin, reduced it to vowels and consonants, and counted the transitions, all to win an argument with Nekrasov, who had claimed statistical regularity in human behavior proved free will because the law of large numbers needed independent events. Markov built dependent chains that obeyed the law anyway, using a poem.

Poker

Then partially observable decision processes, which is where this starts describing the world I actually live in. In an MDP you can see the whole state. In a POMDP you cannot, so you carry a belief over the states you might be in and update it every time something happens.

Poker is the example that stuck. You see your cards and the chips. You do not see anyone else's cards. So you are playing a belief and revising it every time someone acts.

And you pay to see the next card. Which is the other thing I was reading about.

The $10,000 MRI

Value of information says more data is not automatically good. Data costs something, so getting it is a cost-benefit question:

$$\text{VOI}(o) = \mathbb{E}\big[\max_a U \mid o \big] - \max_a \mathbb{E}\big[U\big]$$

The best you could do once you know the observation, minus the best you can already do without it.

The example that made it land: you are offered an MRI. It costs $10,000 and it will tell you exactly what is wrong with you. But whether or not you take it, the doctor is going to tell you the same thing and do the same thing.

If the best action is the same no matter what the scan says, those two terms are equal, so the whole thing is zero. Perfect information, worth nothing, and you are down $10,000 for it. Information is only worth what it changes about what you do.

Poker is doing double duty here. Paying to see another card is exactly this question, every hand.

Back to the agents

Laid out in order these stop looking like separate topics. A chain is things evolving with nobody deciding. An MDP is deciding with full sight of the state. A POMDP is deciding without it. Value of information is whether the next look is worth its price. And causality is the one that breaks the pattern, because you cannot get it by watching:

$$P(Y \mid \text{do}(X)) \neq P(Y \mid X)$$

Setting $X$ is not the same as finding $X$. The left side needs you to reach in and change something. The right side is available from logs.

Which puts the startup idea somewhere interesting. Breaking an agent to learn why it failed is the left side. We arrived at the one thing observation cannot give you by trying to build a debugging tool.

I have watched the right side fail. At work an agent's scores sat at chance level and the metric told me nothing, because the real cause was upstream: speaker diarization was collapsing and merging every speaker into one. No amount of correlating scores against each other would have found that. I had to go change something and watch what moved.

So that is where I am. Reading Kaliel Williamson's Decision-Relative Observation Quotients for Sequential Control with the goal of extending it, and running small experiments to get the foundations under my hands instead of just in my notes. It takes the bigger view, that knowing why beats correlation or more data, and it happens to sit right on top of everything above.

Still learning all of it. More once I have something of my own to add.