Representation and Invariance in Reinforcement Learning

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "Representation and Invariance in Reinforcement Learning".

Jane: The paper was written by Samuel Allen Alexander and Arthur Paul Pedersen from Independent Researcher and The City University of New York.

Tom: Stay tuned as we take you through the paper and discuss its implications.

Title: Tom: Welcome back, everyone. Today we’re digging into a paper that’s been making the rounds on arXiv, and it’s called “Representation and Invariance in Reinforcement Learning.” Jane, I’ve got to say, the title alone got me excited.

Jane: Oh, absolutely, Tom. And I think the title is actually doing a lot of work here. It’s not just about reinforcement learning in the abstract. It’s asking whether the way we *represent* RL — the formal rules we pick — actually changes what the agents can do.

Tom: Right, and that’s a big deal, because in the field, people talk about RL like it’s one thing. You have an agent, an environment, rewards, actions. But the authors, Samuel Allen Alexander and Arthur Paul Pedersen, they’re saying, hold on, the details matter.

Jane: Exactly. And the word “invariance” is the key. They want to know: if you change the rules of the game, does the relative intelligence of agents stay the same? If agent A is smarter than agent B in one framework, is that still true after you convert them to another framework?

Tom: So it’s like, if you take a chess grandmaster and make them play checkers, are they still a grandmaster?

Jane: That’s the spirit, but even more subtle. Because in RL, you’re not just changing the game. You’re changing the language the game is written in. And the authors show that sometimes, that language change actually breaks the comparison.

Tom: And that’s the provocative part. They’re not just saying, “be careful.” They’re showing concrete cases where two perfectly standard RL frameworks are not equivalent. No transformation exists that preserves relative intelligence.

Jane: Which, if true, means the field has been a bit sloppy. People publish results in one framework and assume they apply to another. This paper says, maybe not.

Tom: And that’s why I’m excited. This is foundational work. It’s not a new algorithm that gets you two percent better on a benchmark. It’s asking whether the whole edifice is built on sand.

Jane: Right. And the authors are careful to say this is a first step, a modest stab, as they put it. But it’s a step that could change how we interpret a huge body of research.

Tom: So, Jane, before we get into the guts of the paper, what’s the one thing you want listeners to take away from the title itself?

Jane: That “representation” isn’t a neutral choice. How you set up the rules of RL — deterministic or stochastic, integer or real rewards — that choice has consequences. And “invariance” is the property we’d like to have, but the paper shows we don’t always get it.

Tom: And that’s the hook. Next segment, we’re going to look at the actual summary and the big claims they make. Stick around.

Summary: Jane: Welcome back. We’re still on “Representation and Invariance in Reinforcement Learning,” and now we’re looking at the summary of what the paper actually claims.

Tom: And Jane, the summary is punchy. They introduce this idea of a “transformation” between RL frameworks. It’s a way to convert agents and environments from one setup to another, and they say if such a transformation exists, then relative intelligence is preserved.

Jane: Right. So imagine you have a lab that builds agents for one version of RL, but you have environments built for a different version. You can’t just plug them together. You need a translator. And the paper says, if you can build a good translator, then the smart agents stay smart.

Tom: But here’s the kicker. They don’t just define this. They actually test it on four concrete RL frameworks. And these aren’t exotic. These are the standard ones: deterministic agents, stochastic agents, deterministic environments, stochastic environments.

Jane: And the results are, frankly, a little alarming. Out of twelve possible pairs, only five have a transformation in one direction. And no two frameworks are mutually transformable. So none of the four are equivalent to each other.

Tom: That’s huge. I mean, in practice, people use pseudo-random number generators to make deterministic agents act stochastic. They assume it’s the same thing. This paper says, mathematically, it’s not.

Jane: And the key technical tool they use is something called an ultrafilter. Now, that sounds scary, but the paper explains it in terms of elections. Imagine environments are voters, and they’re voting on which agent is smarter.

Tom: And the ultrafilter is the rule for deciding who wins the election, even when there are infinitely many voters.

Jane: Exactly. And it turns out, this election-based approach to comparing intelligence was proposed by one of the authors, Alexander, in an earlier paper. So this is a continuation of that line of work.

Tom: So the summary is: they define a rigorous notion of reducibility between RL frameworks, they prove that this notion preserves intelligence comparisons, and then they show that the four most common frameworks fail to be reducible to each other.

Jane: Which is a strong statement. It’s not saying one framework is better. It’s saying they’re genuinely different, and we can’t pretend otherwise.

Tom: And I love that they’re honest about the limitations. They say, look, we only looked at integer rewards. We don’t know if this holds for rational rewards. That’s the kind of humility you don’t always see.

Jane: Right. And that’s actually a perfect segue, because next we’re going to look at the first page of the paper, where they lay out the motivation and the questions they’re asking. That’s where the real philosophical meat is.

Tom: And I can’t wait. Because the questions they ask on that first page are the ones that keep me up at night.

Improvements: Tom: We’re back, still on “Representation and Invariance in Reinforcement Learning.” And Jane, we’ve talked about the title and the summary. Now I want to get into what this paper actually improves on. What does it add to the field?

Jane: Great question, Tom. And I think the biggest improvement is that it gives us a *language* for talking about equivalence. Before this paper, if someone said “these two RL frameworks are basically the same,” there was no formal way to check that claim.

Tom: Right. It was all vibes. Someone would say, “Oh, deterministic agents are just a special case of stochastic agents,” and everyone would nod along.

Jane: And this paper says, okay, let’s make that precise. Let’s define what it means to convert one framework into another, and let’s prove whether that conversion preserves the thing we care about — relative intelligence.

Tom: And that’s a real improvement, because it turns a philosophical debate into a mathematical one. You can’t just assert equivalence anymore. You have to exhibit a transformation, or prove none exists.

Jane: Exactly. And they also improve on the existing intelligence measurement literature. The Legg-Hutter intelligence measure, which is famous, is mathematically unwieldy. It involves infinite sums and Kolmogorov complexity, which is noncomputable.

Tom: So it’s beautiful but impractical.

Jane: Right. And the ultrafilter approach they use is more tractable. It lets them actually prove preservation theorems, which they couldn’t do with the Legg-Hutter measure.

Tom: And there’s another improvement I want to highlight. They introduce this notion of “well-behaved environments.” Because the naive definition of expected total reward doesn’t always converge. You can get infinite sums that blow up.

Jane: Oh, that’s a good point. So they restrict attention to environments where the value function is guaranteed to converge. That’s a practical fix that makes the theory usable.

Tom: And it’s not just a technical trick. It’s a real modeling decision. In practice, you don’t want agents in environments where rewards diverge to infinity. You want well-behaved ones.

Jane: So the improvements are: a formal notion of reducibility, a tractable way to compare intelligence, and a clean way to handle convergence issues. That’s a solid contribution.

Tom: And the payoff is that they can now prove something surprising: that the four standard frameworks are not equivalent. That’s the result that’s going to get people talking.

Jane: And it’s going to get people arguing, too. Because some of those negative results are counterintuitive. Like, why can’t you map stochastic agents into deterministic ones? That seems like it should be easy.

Tom: Right, and that’s exactly what we’re going to dig into next, when we look at the first page of the paper and the specific questions they raise. That’s where the real fireworks are.

First Page: Jane: Welcome back to the show. We’re still on “Representation and Invariance in Reinforcement Learning,” and now we’re looking at the first page, where the authors set the stage.

Tom: And Jane, the first page is basically a manifesto. They start by asking, “If we changed the rules, would the wise become fools?” That’s the opening line, and it’s fantastic.

Jane: It really sets the tone. And they immediately get concrete. They ask: what if rewards are only zero? Clearly weaker. What if rewards are only zero and one? What about −one zero one? What about all integers? What about rationals? What about reals?

Tom: And they admit they don’t know the answers. They say this is a “modest first stab” at the problem. But the questions themselves are the contribution.

Jane: Right. Because those questions force you to realize that the details of RL aren’t arbitrary. They’re design choices, and those choices have consequences.

Tom: And then they introduce the four frameworks we’ve been talking about. Deterministic agents, stochastic agents, deterministic environments, stochastic environments. Four combinations.

Jane: And they say, look, all four are used in practice. Deterministic agents often masquerade as stochastic through pseudo-random number generators. So if these frameworks aren’t equivalent, that’s a real problem.

Tom: And the first page also mentions the broader context. They cite Silver et al., who wrote “Reward is enough,” arguing that RL will lead to AGI. And the authors here are saying, well, which RL?

Jane: That’s the key question. If the formal details matter, then you can’t just say “RL will lead to AGI.” You have to say *which* RL, with *which* rewards, *which* action spaces, *which* convergence criteria.

Tom: And that’s a profound point. Because the AGI debate is often conducted at a high level of abstraction, and this paper drags it down to the gritty details.

Jane: It does. And I think that’s healthy. Because if we’re going to make grand claims about intelligence, we need to be precise about what we mean.

Tom: And the first page also sets up the structure of the paper. They’re going to define transformations, they’re going to introduce ultrafilters, and then they’re going to prove the main theorem about the four frameworks.

Jane: Which we’ve already spoiled, but that’s okay. The journey is the fun part.

Tom: And the journey includes some genuinely surprising results. Like, you can map deterministic agents into stochastic agents, and you can map stochastic environments into deterministic environments. But you can’t do the reverse.

Jane: And that asymmetry is the kind of thing that makes you go, “Wait, really?” And that’s the hook for our final segment, where we wrap up and talk about what this all means.

Conclusion: Tom: And we’re back for the final segment on “Representation and Invariance in Reinforcement Learning.” Jane, let’s pull it all together.

Jane: Let’s do it. So the paper gives us a formal way to ask whether one RL framework can be reduced to another. It defines transformations, proves that those transformations preserve relative intelligence, and then shows that the four standard frameworks are not mutually reducible.

Tom: And the key result is that asymmetry. You can go from deterministic agents to stochastic agents, and from stochastic environments to deterministic environments. But not the other way around. And that’s a genuinely new finding.

Jane: It is. And it suggests that the choice of whether agents are deterministic or stochastic isn’t just a convenience. It’s a fundamental design decision that changes the mathematical landscape.

Tom: And the implications for the field are big. Researchers need to be more careful when they say “reinforcement learning” as if it’s one thing. They need to specify which framework they mean.

Jane: And that’s not just pedantry. It affects how we interpret results, how we compare agents, and even how we think about the path to AGI.

Tom: Right. Because if the frameworks aren’t equivalent, then a result proven in one framework might not transfer to another. And that’s a warning shot across the bow.

Jane: But the authors are also humble. They say this is an initial step. They only looked at integer rewards. They don’t know if the results hold for rational rewards. So there’s a lot of open work.

Tom: And that’s exciting. This paper opens up a whole research program. What about real-valued rewards? What about multi-agent RL? What about non-Archimedean rewards?

Jane: Exactly. And that’s why I’m glad we covered this paper. It’s not a flashy result. It’s a foundational one. It’s the kind of paper that might not get a thousand citations, but it changes how the people who do cite it think.

Tom: Well said, Jane. So that’s “Representation and Invariance in Reinforcement Learning” by Samuel Allen Alexander and Arthur Paul Pedersen. We’re going to say goodbye to this paper and get ready for the next one.

Jane: And we hope you enjoyed the discussion as much as we did. Thanks for listening, and we’ll see you next time.