acceptodds
Under review as a conference paper at ICLR 2027

When Do Intrinsic Rewards Lead to Exploration?

Abstract

Intrinsic rewards are designed to guide exploration in reinforcement learning by assigning value to an agent's experience, for example through prediction error or learning progress. However, maximizing these rewards need not produce the most informative experience available. We propose a formal criterion for exploration that compares policies by the counterfactual information they acquire: how well their histories can substitute for experience under alternative policies. We construct a single, simple environment in which specified count-based, prediction-error, empowerment, and information-gain objectives have maximizing policies that are Pareto-suboptimal at acquiring counterfactual information. We explain these failures and establish conditions under which existing intrinsic rewards successfully encourage optimal exploration. We also construct an objective that assigns a higher value whenever exploration strictly improves under our criterion.

Primary area:
reinforcement learning
Keywords:
exploration, intrinsic motivation, reinforcement learning, counterfactual learning, comparison of statistical experiments, information gain

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_qnv3OpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

The paper discusses a very interesting and novel view of exploration. A policy is a good exploration policy if the data collected using that policy is useful to predict the outcome distribution of all other policies. Their main technical contribution is that they show 1) many popular exploration methods don't maximize this notion of exploration, and 2) maximizing information gain (with a certain objective) is a reasonable surrogate objective for this notion of exploration under certain assumptions. They also introduce an interactive exploration bonus and calculate it for some very simple and small MDPs with known dynamics.

Critical strengths
  1. The notion of exploration they introduce is really interesting and novel. While conceptually very similar to epistemic uncertainty, it is truly a new way to look at epistemic uncertainty that I haven't seen in teh literature before.

  2. The main theorem (Thm4.1) result is interesting and definitely non-trivial. Showing a connection between information gathering and the notion of exploration through producing good counterfactuals is very interesting and novel.

  3. Their analysis in sec 3.2, where they show certain information gathering objectives prefer getting less number of information that are presented to them in multiple steps than one big chunk of information presented over one step, is very interesting. I haven't seen this result before, and this raises serious concern about using some og these objectives, a concern that no prior work has introduced based on my knowledge.

Critical weaknesses

While I find the conceptual formulation of the paper very interesting and thought-provoking, I don't think this paper deserves an accept for three reasons:

  1. The paper is extremely badly written. I had a horrible time understanding their results. In the Intro section, they start motivating their problem with an interesting example. The example itself is very intuitive and straightforward, but unfortunately they do a very bad job explaining it such that the example sounds too complicated, and only through reading again and again can one decode what the example is, and only then does it become so evident that they are explaining a very intuitive problem in a very unintuitive way. The rest of the paper is very badly written too. Most claims and explanations are presented without first giving enough context or using language that is unnecessarily technical and not understandable. The theorem statements are basically unreadable. If I were the author, I would consider a major edit to the writing.

  2. My second big problem with the paper is that although their conceptual contribution is interesting, their objective is completely incomprehensible and they don't even make a simple attempt to present a tractable version of it. Reading their paper, I conjecture that using generative adversarial style objectives, it should be possible to obtain a tractable approximation of their method, but they didn't make any effort to obtain such algorithms, and this doesn't allow us to understand if this method is merely an interesting mental model or is actually something useful.

  3. Finally, I find that some of the claims of the paper are not novel, and at the same time they don't acknowledge that these concepts have existed in the literature before; for instance, their discussion about novelty-seeking exploration methods could be summarized as the difference in aleatoric and epistemic uncertainty methods, which has been discussed in many prior RL exploration works. Their random color generator example is exactly equivalent to the popular noisy TV example in RL. Their notion of exploration is conceptually very similar to epistemic uncertainty, and they fail to mention that connection. I agree the paper presents a novel view of this kind of uncertainty, but I don't like the fact that they don't acknowledge that a big part of these concepts have been laid out by prior works. Overall, the framing of the work in the context of prior works is really weak and non-comprehensive.

Questions for authors
  1. Can you try a tractable approximation of the method by training three models concurrently as follows:
  • A decoder model that predicts the future of a dictionary of policies
  • An adversarial policy that tries to add new policies to the policy dictionary such that the decoder has a very high error on those policies
  • An exploratory policy that is rewarded for collecting trajectories that reduce the encoder error

I understand the main contribution of the paper is theoretical, and it is indeed an interesting theoretical work, but some attempt to at least propose a tractable approximation of the method would significantly strengthen the work.

2 comments

Thank you for the careful reading and the specific suggestions. In short, we rewrote the exposition, we ran the three-model experiment you proposed (Appendix I.4), and the paper now states its connection to the noisy TV and to epistemic uncertainty.

1. The writing

The example itself is very intuitive and straightforward, but unfortunately they do a very bad job explaining it [...]

We agree, and the revision rewrites the exposition. The introduction now describes the example in words before any notation and states its conclusion directly after Figure 1, and we removed the random startup bits that obscured it. Sections 2 and 3 open with concrete cases, each theorem is preceded by one sentence in plain words, and Table 1 gives one number per objective.

2. A tractable version

Can you try a tractable approximation of the method by training three models concurrently [...]

The score in §5 is an existence result and not a proposed training objective, which the reviewed version left too implicit. It shows that a single number can rise with every strict improvement in exploration, and Proposition H.1 shows that no algorithm can approximate such a score to any requested accuracy for every computable policy.

Two things are already available. On a finite class of worlds, each with positive prior probability, a familiar objective is aligned with the criterion, because cumulative information gain rises with every strict improvement (Theorem 4.1). And for a supplied finite world model with a fixed list of targets and a fixed collection budget, §6 computes finite versions of the score numerically.

We also tried your three-model proposal, in a tabular setting with two hidden bits (Table 3). We trained a collector, one decoder per target policy and a target generator from sampled episodes, and then audited the collector against exact errors from linear programming. In two of three environments its worst error over all 27 targets, averaged over six seeds, is within 0.0002 of the optimum under the same minimum action probability, and in the third, which has noisy readings, it reaches 0.094 against 0.078. It also keeps its first-action probability of requesting a fair coin near the minimum allowed, so it does not chase noise. Three caveats apply: the fitted decoders stayed weaker than the optimal ones used in the audit, the learned generator added little over keeping the hardest of four random candidates, and training used labelled reset episodes from every world, so the pilot shows that your loop is well posed but not yet that it is practical.

The version with neural networks that we have in mind keeps your three parts: a recurrent collector; a sequence model as decoder, which reads the collector's history and predicts each next target observation; and a proposer of target policies, rewarded for the decoder's excess error over a second decoder that is told the world, a baseline meant to remove the reward for noise. We have not implemented it, and we think it is a separate paper because of four obstacles. The loss is a total variation distance between distributions over histories, which is hard to estimate from samples once histories are long. The criterion takes the worst case over worlds, and sampled worlds give no guarantee for unsampled ones. Training compares collector and target runs in the same world, which requires resetting it. And the space of target policies grows very quickly, since §6 already has 32,768 four-step targets.

3. Prior work

Their random color generator example is exactly equivalent to the popular noisy TV example in RL. Their notion of exploration is conceptually very similar to epistemic uncertainty [...]

You are right, and we should have said so. The random color is a noisy TV (Burda et al., 2019), and a reward for it is a reward for aleatoric uncertainty (Mavor-Parker et al., 2022), which the introduction now states. The Shannon, Square and count results in §3.1 are therefore versions of that known failure. Three other results are not: empowerment ignores the color, yet each of its maximizers keeps the display with positive probability because it is rewarded for controlling the digit; the four-bit example in §3.2 has no noise, yet Hellinger and Absolute still prefer three bits one at a time to four at once; and information gain, which counts only epistemic uncertainty, still ties inspection with play under the complete return (§3.3).

On epistemic uncertainty, §7 now says that expected information gain measures the epistemic uncertainty removed on average over worlds under a prior, whereas our criterion requires simulation in every world and chooses no prior. Theorem 4.1 relates the two on finite classes, and the alarm shows that they can separate on an infinite one: after a long silence the average uncertainty is nearly zero, but at every time some world still has its alarm ahead.

Thanks for the authors' response.

One of my main concerns was about the poor presentation of the paper. Although the authors have made some changes, I still find the paper very hard to follow. For instance, starting a paragraph with the sentence "An alarm may ring once after an unknown delay or never" is genuinely a bad idea, as the reader has no context for what this means.

We study exact reward maximizers to separate these incentives from the difficulty of learning an optimal policy.

This is another example of such a hard-to-read sentence; there are many of them in the paper, unfortunately.

Your tabular experiment is interesting, but I have two concerns. First, the presentation of this experiment in the paper is very unclear, to the point that I couldn't understand it just by reading the paper. Perhaps adding a figure would help make the setup and results easier to understand.

Second, I don't agree that implementing a simpler version of this approach with neural networks would be very difficult. For example, the difficulties you mentioned could be addressed as follows:

Total variation distance between distributions over histories.

You don't need to measure this accurately. You could train a model that takes a policy index and generates trajectories of that policy, then compare these generated trajectories with ground-truth trajectories. The average distance between them could serve as a rough measure of how well the model captures the trajectory distribution. If both the policy and environment are deterministic, this comparison could be almost exact.

The criterion takes the worst case over worlds, and sampled worlds give no guarantee for unsampled ones.

In practice, you could simply measure, on average, how well a model can predict the future trajectories of other policies. It doesn't necessarily have to be a worst-case criterion.

Training compares collector and target runs in the same world, which requires resetting it.

You could train many target policies as probes that expand the frontier of exploration, alongside one collector policy whose only objective is to collect informative data. This would look somewhat like self-play.

Overall, although the authors' clarifications were helpful and the fact that they added the needed prior works to their paper is appreciated, I still don't find the presentation and results of the paper ready for publication at ICLR. I think the theoretical contribution of the paper alone, at least in the way it is presented now, isn't enough for publication, and I do believe that with substantially better presentation and with even a very simple didactic neural network-based experiment, their paper could be great.

Reviewer_tRNLOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper shows that different types of intrinsic rewards, such as count-based, prediction-error-based, and skill-learning-based rewards, do not necessarily lead to the most informative exploration. To address this, the authors propose a new definition of good exploration by comparing policies based on their ability to reproduce the history distributions of alternative policies using the information they collect.

They demonstrate several failure modes of existing intrinsic rewards and propose a general simulation-error-based score that preserves every strict improvement in exploration according to their criterion.

Critical strengths
  1. A principled theoretical framework and objective for evaluating intrinsic exploration.

I think the proposed definition of good exploration is useful, as there is a need for more principled ways to evaluate and compare intrinsic exploration methods. It is not always clear which intrinsic reward methods lead to more informative exploration. The authors propose both a theoretical framework for defining what constitutes good exploration and an objective function that preserves strict improvements in exploration according to this definition. I find this a valuable contribution, as it provides a more principled way to reason about and compare different exploration objectives.

  1. Interesting analysis of the failure modes of existing intrinsic rewards.

It is interesting to see the failure modes of different categories of intrinsic rewards, such as count-based, prediction-based, and skill-learning-based methods, and how they can diverge from actually acquiring useful information. I particularly liked the alarm example, which provides an intuitive way to understand why some intrinsic rewards may favor less informative exploration.

Critical weaknesses
  1. The paper is somewhat difficult to follow.

I found the paper a bit hard to digest due to the technical presentation. In particular, the connection between the formal definition of exploration and the implications of the theoretical results could be explained more intuitively. I think simplifying some of the explanations and adding more intuition around the main results would make the paper more accessible to a broader RL audience.

  1. Limited practical applicability.

The empirical results are mainly a proof of concept, and as the authors themselves acknowledge, broad empirical superiority has not been established. I understand that the main contribution is the theoretical framework and analysis, but this leaves open the question of how much we can benefit from the proposed framework in practice, especially given the computational limitations of the general objective. It would strengthen the paper to discuss more concretely whether tractable approximations could be developed and under what assumptions.

Questions for authors
  1. Practical approximation of the proposed objective.

Given the computational limitations of the native score proposed in Section 5, do the authors envision any tractable approximations of this objective that could be translated into a practical RL algorithm?

  1. Connection to downstream performance.

How does the proposed exploration criterion relate to sample efficiency or downstream task performance? Is a policy that is more informative according to this criterion necessarily better for downstream tasks, or would additional assumptions be needed to establish such a connection?

2 comments

Thank you for the review, and for the comment on the alarm example. We simplified that example further in the revision, and the note to all reviewers lists what changed as a result.

1. Intuition for the definition and results

the connection between the formal definition of exploration and the implications of the theoretical results could be explained more intuitively.

The introduction is rewritten around this connection. It now says what the definition is for: if one policy's history can reproduce another's, then any later choice that would have used the second history can be made from the first, with nearly the same expected payoff.

In addition, §2 and §2.2 now open with concrete cases, §3 says what attracts each reward before stating results, and each theorem is preceded by one sentence in plain words.

2. Tractable approximations

Given the computational limitations of the native score proposed in Section 5, do the authors envision any tractable approximations of this objective that could be translated into a practical RL algorithm?

Yes, under three kinds of assumption, listed from the most to the least we can prove.

  1. On a finite class of worlds, each with positive prior probability, cumulative information gain rises with every strict improvement in exploration (Theorem 4.1). That result concerns the exact complete return, so it identifies information gain as a sound target in this setting without guaranteeing a particular approximation such as VIME.
  2. Given a supplied finite world model, a fixed list of targets and a fixed collection budget, the native objective is computable, and §6 computes it numerically on 22 classes (Appendix I).
  3. With sampled episodes in place of a supplied model, we followed Reviewer qnv3's proposal and trained a collector, decoders and a target generator on three two-bit environments (Appendix I.4, Table 3). In two of them the collector's mean worst error over six seeds is within 0.0002 of the numerical optimum under the same minimum action probability, and in the third it reaches 0.094 against 0.078. Training used labelled reset episodes from every world, so this checks that the training loop is well posed, but it is not yet a practical algorithm.

Turning the third item into a practical RL algorithm would mean replacing its tables with networks: a recurrent collector, a sequence-model decoder and a target proposer, as sketched in our reply to Reviewer qnv3. That version would face obstacles beyond scale. The simulation error is a total variation distance, which is hard to estimate from samples once histories are long. The criterion needs the worst case over worlds, and sampled worlds give no guarantee for unsampled ones. And training compares collector and target runs in the same world, which requires resetting it. We think that overcoming these is a separate paper.

We do not claim a general algorithm, because Appendix H (Proposition H.1, "Evaluation obstruction") shows that no algorithm can approximate a strictly monotone score to any requested accuracy for every computable policy, since that would decide the halting problem. The result needs the score to be strict on only one comparison. For this reason we see the criterion's present practical use as a test for objectives, as in Table 1.

3. Downstream performance

Is a policy that is more informative according to this criterion necessarily better for downstream tasks, or would additional assumptions be needed to establish such a connection?

For later decisions the answer is yes, meaning at least as good given enough collection time, and it needs no assumption beyond finitely many choices and bounded payoffs. The new Appendix K states this in three steps.

  • Suppose a collected history reproduces another experiment with simulation error ε. Then, for any finite set of choices and any payoffs in [0, 1], a choice rule built for the other experiment loses at most ε in expected payoff when it is run on the reproduced data (Theorem K.1).
  • This bound cannot be improved, because the simulation error equals the supremum of such losses over all finite decision problems and finitely supported priors (Theorem K.2).
  • As a consequence, a policy explores completely exactly when, for every fixed budget and every ε, there is a collection time after which it comes within ε of the best payoff any policy could obtain within that budget, in every decision problem at once (Corollary K.3).

The guarantee has two limits. First, it concerns choices informed by the collected evidence, judged from the original starting point, so it does not cover reward earned by continuing the same run. On the alarm, for instance, inspecting turns the display off for good. Second, it is not a sample-efficiency result, because the collection time may exceed the alternative's budget.

Reviewer_tRNLOpenReview ↗

Reviewer Follow-up: Maintaining Original Recommendation

Thank you to the authors for the detailed response and revisions. I appreciate the additional intuition, clarification of the connection to downstream performance, and discussion of practical approximations and their limitations. While my concerns about practical applicability remain, I maintain my original score.

Reviewer_NJZWOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

I am afraid I cannot give a good summary, given how poorly the paper has been written, but I will attempt it as follows: The paper examines histories under different worlds and attempts to make some observations about different exploration policies, including those that are derived from various different intrinsic reward functions, with the objective of developing a formal definition of exploration.

Critical strengths

I am afraid I cannot state any critical strengths that would support acceptance.

Critical weaknesses

The paper does not clearly state its objectives, the motivation for these objectives, and how the paper makes a significant advance in the field. One claim is that the paper proposes a formal criterion for exploration; it is unclear why this criterion is needed and how it will be useful. One question raised in the introduction is: "Can a reward-maximizing policy be strictly dominated—can another policy reproduce all its finite history distributions while the reverse fails?" It is unclear why this question is important to answer or how the answer will be useful. A reward-maximizing policy, by definition, acts to maximize reward; consequently, it can fail (or perform poorly) at other objectives.

There is a single, simple example used throughout the paper, one that is not explained clearly. It is unclear why this single example is so prominent or what can be concluded from it regarding what the authors are aiming to find out.

I found the paper very difficult to follow and had to read many sentences/paragraphs multiple times.

Questions for authors

I have no questions at this time that can materially affect my assessment.

1 comment

Thank you for the review. We agree that the paper was hard to follow, so we have rewritten the introduction, the example and the main table, and the note to all reviewers lists each change. Since your points concern what the paper is for and why its example matters, we answer each of them briefly below.

1. Objective, motivation and use

The paper does not clearly state its objectives, the motivation for these objectives, and how the paper makes a significant advance in the field. One claim is that the paper proposes a formal criterion for exploration; it is unclear why this criterion is needed and how it will be useful.

Intrinsic rewards are meant to make an agent explore when no task is given. To ask whether they succeed, one must be able to say when one policy explores more than another without choosing what the evidence will be used for. We give such a comparison: a policy explores at least as much as another if its data can reproduce the other's data in distribution, in every possible world.

This comparison is the right measure when the later use is unknown, because the reproduction error equals the supremum of the losses over later decisions made from the data (Appendix K).

With this comparison in hand, the paper reports three kinds of result. Table 1 shows where existing rewards fail, Theorem 4.1 shows when information gain is guaranteed to succeed, and Theorem 5.1 together with Appendix H shows that a score rewarding every strict improvement exists but cannot be computed in general.

2. Why ask whether a reward maximizer is dominated

It is unclear why this question is important to answer or how the answer will be useful. A reward-maximizing policy, by definition, acts to maximize reward; consequently, it can fail (or perform poorly) at other objectives.

We agree that a reward maximizer can do poorly on other objectives. The rewards we study, however, are proposed specifically as ways to produce exploration, so asking whether their maximizers gather the most evidence tests each reward at its own purpose. The answer turns out to differ by reward, and that difference is what the paper reports.

3. The example

There is a single, simple example used throughout the paper, one that is not explained clearly. It is unclear why this single example is so prominent or what can be concluded from it.

The example is prominent because it isolates one situation: one action yields evidence about the world, while the other yields only variety, namely a random color, a digit the agent controls, and more observation labels.

What can be concluded from it is that none of the count, prediction-error and empowerment objectives in Table 1 is maximized by always taking the evidence, even though, at any finite time, a policy that skips it has worst-case error one half on whether the alarm will ever ring.

The paper uses other examples only where a reward needs a different setting: rewards defined on states need a Markov decision process, and the four-bit example tests the order in which evidence arrives.

4. Readability

I found the paper very difficult to follow and had to read many sentences/paragraphs multiple times.

The other two reviewers said the same, and the revision is a rewrite of the exposition for that reason.

Comments on the paper

1 comment

We thank the three reviewers. All three found the paper hard to follow, and beyond that, Reviewers tRNL and qnv3 asked for a tractable version of the reference score, while Reviewer qnv3 also asked how the work connects to prior work on noise and uncertainty. The revision addresses each of these points. Because it changes more than wording, we list the changes here.

Rewritten

  • The introduction now states the aim first: to say when one policy explores more than another without choosing what the evidence will be used for. A policy explores at least as much as another when its data can reproduce the other's to any accuracy, in which case any decision the other's data could inform can be made nearly as well from its own (Appendix K). The introduction then presents the example and states its conclusion after Figure 1.
  • Figure 1 is redrawn, and Table 1 now gives one number per objective, namely the worst error among its maximizers.

The example is simpler

  • The alarm no longer adds random bits at startup, and the display and alarm readings now arrive in the same step. The possible worlds, the three actions, and the result for inspection are as before.
  • As a consequence, two results are restated. The reviewed version stated the predictive Shannon and Square results for every discount, whereas they are now stated for finite horizons (at least 2 observations for Shannon and 3 for Square), with the complete returns treated separately (§3.1; Proposition D.1 in Appendix D).
  • The count-bonus proof is redone for the new observation labels, with the same threshold of 64 observations (Proposition C.2 in Appendix C).

Added

  • Appendix K states what the criterion means for later decisions, using classical results of Blackwell and Le Cam with proofs for our setting.
  • Appendix I.4 reports a small learning experiment that follows Reviewer qnv3's proposal (Table 3).
  • The introduction now names the noisy-TV problem and the distinction between aleatoric and epistemic uncertainty, and §7 relates our criterion to information gain and to other methods that target epistemic uncertainty.
  • Empowerment is now computed from the whole block of observations and scored by its complete return, whereas the reviewed version kept only the final observation and used a long-run average or discounted return (§3.1; Proposition C.3 in Appendix C).
  • §3.2 adds a learning-progress reward, Bayesian prediction gain, with a separate two-world example (Proposition F.1 in Appendix F).

Retained

  • The definitions in §2, the assumptions and conclusions of Theorems 4.1 and 5.1, the four-bit comparison, the computability obstruction, and the 22-class finite planning study in §6 are retained, although the prose around them has been rewritten.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.