Outcome-Based Online Reinforcement Learning: Algorithms and Fundamental Limits

We thank the reviewer for the review. Below, we address the concerns raised in the review:

The central contribution, Algorithm 1, hinges on solving a joint optimization problem (Eq. 6) to estimate the value and reward functions. While theoretically elegant, this step poses significant practical challenges. The objective function itself involves a Bellman loss term, which requires computing an infimum over function class . This creates a nested, max-min-like optimization problem. In the general function approximation setting, where and are typically non-convex (e.g., neural networks), solving this outer maximization for a global optimum is generally intractable.

We admit that to solve the optimization problem in Algorithm 1 can be computationally intractable without proper assumptions. Broadly speaking, in the literature of RL theory, achieving computational efficiency RL with general function approximation has long been an open problem. To the best of our knowledge, it is only partly resolved under restricted problems (e.g., MDPs with linear structure) or stronger access oracle (reset).

We note that under reset access, the max-min optimization in our algorithm can indeed be replaced by a maximization problem, following the approach of [A]. Achieving computational tractable outcome-based RL beyond the setting of reset access can be an important direction of future work.

On the Computational Feasibility of Algorithm 1: Beyond the special case of deterministic MDPs, could you elaborate on potential pathways to make this optimization computationally feasible, even if it requires approximations? For example, are there specific structural assumptions on the function classes (beyond determinism) or approximation techniques (e.g., alternating optimization, gradient-based methods for the outer loop) that you believe could make Algorithm 1 practical?

As mentioned above, with reset access, the algorithm can be modified to avoid the max-min optimization. In addition, gradient-based approximation/alternating optimization can indeed be applied to the max-min optimization problem, assuming that the function classes are parametrized (e.g., class of neural networks). Particularly, under certain regularity conditions, the existing convergence results may be applied, showing that a local minima can be found. We believe analyzing the optimization landscapes of the GOLF-based algorithms is an important future direction for RL theory.

[A] The Power of Resets in Online Reinforcement Learning. Zakaria Mhammedi, Dylan J. Foster, Alexander Rakhlin.

We thank the reviewer for the detailed review. Below, we address the concerns raised in the review:

Line 39 Meaning of "well structured" or “well behaved” reward functions

We use this adjective to describe that the reward function is either linear with respect some features of state-action pairs, or slightly more generally, admitting bounded trajectory eluder dimension. Assumptions on well-behaved reward function is very common in previous work, including in tabular MDP (where the reward function is automatically linear with respect to the $|\mathcal{S}|\times |\mathcal{A}|$-dimensional feature) and linear MDP (where the linear reward function is part of the linearity structure).

We will clarify this in the revision.

Line 126 Bellman operator as the heading?

Thanks for the suggestions. We will update it in our revision.

Line 175 what’s $d$?

In the setting where the function classes are parametric, $d$ is the dimension of the parametric model, i.e.. the number of “free parameters”. For example, when the function classes are linear with respect to a feature map, $d$ is the dimension of the feature.

Line 256 and Line 300

Thanks for pointing out the typo, we will fix them in the version.

Reason and choice of reference policy in Alg1 and Alg3

The point of adopting the policy $\pi\circ_h \pi_{\mathrm{ref}}$ is to make the algorithm more exploratory. The fixed reference policy serves as a comparator for the policy $\pi^{(t)}$, and it has to be the same across different iterations. Based on this reasoning (and our theoretical analysis), we cannot choose $\pi_{\mathrm{ref}}$ to be $\pi^{(t)}$, which changes over time.

We thank the reviewer for the detailed review. Below, we address the concerns raised in the review:

In the loop between steps 4 and 7 of the Algorithm 1, the policy $\pi\circ_h \pi_{\rm ref}$ is executed once per iteration to collect a trajectory. This means that each iteration yields $H$ trajectories in total, and the entire algorithm generates $TH$ trajectories over $T$ iterations. This differs from standard online RL algorithms, which usually collect only one trajectory per iteration.

Indeed, our algorithm collects $H$ trajectories per iteration by executing the policy $\pi\circ_h \pi_{\rm ref}$ for each $h$. This strategy makes the algorithm actively explore the environment. While it is not a standard one in the literature of online RL, such a “per-step” exploration is commonly adopted in the literature on partially observable RL, where active exploration is crucial for sample efficiency guarantee.

As a remark, our algorithm can also be modified so that it only collects one trajectory per iteration, by uniformly sampling a step h and executing $\pi\circ_h \pi_{\rm ref}$. Our analysis can similarly be adopted with such a modified algorithm. However, to keep the presentation as simple as possible, we chose to present the current version of the algorithm.

Some notations are not explained, such as $d^\pi_h$ and $\mu_h$, although they are standard notations in offline learning. …In offline learning, $\mu_h$ usually refers to the data distribution. In the online setting, however, data is generated interactively over time. Could the authors clarify what specifically represents in online RL?

We thank the reviewer for bringing up this subtle point. $d^\pi_h$ is defined to be the occupancy measure at layer $h$. More specifically, for any state $s\_h\in \mathcal{S}\_h$ and action $a_h$, $d^\pi\_h = \mathbf{Pr}\_{\tau\sim \pi}[(s_h, a_h)\in \tau]$, where $\tau$ is a trajectory sampled according to policy $\pi$. Additionally, $\mu_h$ appears in the definition of the coverability coefficient in online learning. The coverability coefficient is defined as

where there is an infimum over all distributions $\mu_1,\cdots,\mu_H$ over $\mathcal{S}\times\mathcal{A}$. By contrast, in offline RL, the sample complexity guarantees typically scale with the concentrability coefficient:

where $\mu\_1,\cdots,\mu\_H$ are the fixed offline data distribution. Therefore, the coverability coefficient equals the smallest possible concentrability among all possible offline data distributions. The above relation between the coverability coefficient and the concentrability coefficient provides a bridge between offline RL and online RL, and the coverability coefficient has been identified as a natural and intrinsic complexity of online RL (see e.g., (Xie et al., 2023), and also [A] and [B]).

In the definition of Bellman completeness, the Bellman operator is applied to vector-valued functions $f (f\_1,...,f\_H)$, whereas in Assumption 2, it is applied to scalar-valued functions $f_{h+1}$.

Thank you for pointing out this typo. We will update the definitions in the revision, so that Bellman operator is defined on the vector-valued function and consistent with the existing work.

In the lower bound proof, the ReLU bandit example (Section 6.1.4) demonstrates a linear sample complexity in $T$. Is this because the example violates Assumption 1 and Assumption 2?

In the ReLU bandit example, both Assumption 1 and 2 are satisfied, but the coverability $C_{\rm cov}=\exp(\Omega(d))$, as the set of all (possibly optimal) actions is exponentially large. We will clarify this in the revision.

References:

[A] The Power of Resets in Online Reinforcement Learning. Zakaria Mhammedi, Dylan J. Foster, Alexander Rakhlin.

[B] Scalable online exploration via coverability. Philip Amortila, Dylan J Foster, Akshay Krishnamurthy.

We thank the reviewer for the review. Below, we address the concerns raised in the review:

Limitations of the analysis or the framework are not discussed.

Thank you for pointing out the omission regarding the limitations of our analysis/framework. We will update them accordingly in the future version of our paper.

Regret is never introduced in the paper. Also the notation $R$ is confusing with reward (e.g. Eq. 11, 13 etc.).

Thanks for mentioning this issue. We will add the following definition in our revision: “The regret across $T$ steps is defined as $\sum_{t=1}^T (V^\star - V^{\pi_t})$, where $V^\star$ is the optimal value function and $V^{\pi_t}$ is the value function of the policy chosen at time $t$.” We will also clarify the notation $R$.

The description of the comparator class is almost non-existent. I understand that the idea comes from another work but explaining how to choose it exactly, specially in preference-based setting, is necessary for clarity.

The comparator class $\mathcal{G}$ for the Bellman completeness is indeed commonly considered in the literature of model-free RL. Typically, it can be chosen to be the value function class $\mathcal{F}$, as long as the class $\mathcal{F}$ is rich enough (so that it is close under the Bellman operator). When the class $\mathcal{F}$ consists of neural networks, we may expect the Bellman completeness holds with small error, as guaranteed by the approximation theory of neural networks.

Can you provide some examples of $N(\alpha)$ and $N_T$ for some function classes? Present description in line 175 is vague to me.

For example, when $F$ is a parametric class of dimension $d$, e.g. $d$-dimensional linear function, we have $\log N(F, \alpha)\asymp d\log(1/\alpha)$. When $F$ is some non-parametric class, e.g. Lipschitz functions in dimension $d$, we have $\log N(F, \alpha)\asymp \alpha^{-d}$.

The proposed lower bound on T to satisfy the error bounds in Eq 7, 10 and 14 seems intangible to me as both sides depend on T, and I do not see how the left side scales with T for some useful function classes. Can you explain this?

As discussed, for parametric function class, we have $N_T\asymp d\cdot \log T$, where $d$ is (roughly) the number of parameters. For such classes, all of these conditions in Eq 7, 10 and 14 with both sides depending on $T$ hold when $T\ge M * \log T^2$ for some parameter $M$ possibly depending on $\epsilon, \delta, H$ and $C_{\rm cov}$. Therefore, this condition is automatically satisfied when $T \ge M \cdot \log^2 M$. This condition can be used as a surrogate condition in Eq 7, 10 and 14. We will clarify this in the revision.

The lower bounds are interesting for future research but no detail or intuition on the "hard" MDP construction is provided. Can you summarise why the specific two-layer MDP constructed exposes this gap? What is the bottleneck?

The main intuition of Theorem 4 (the lower bound) is that, without bounded coverability, the outcome reward may not be well-behaved even when the per-step (process) rewards are generalized linear functions. Technical, the lower bound follows from the following two facts:

• ReLU bandit setting is exponentially hard to learn

• In linear bandit setting, there are algorithms with $O(d\sqrt{T})$ regret

So in our two-layered MDP construction, we let the full problem to be a ReLU bandit, meanwhile we encode a linear reward structure in the first layer. Hence with the per-step reward model, the learner has access to the linear structure in the first layer, hence can achieve sublinear regret, while with the outcome reward model, the learner must deal with the ReLU bandit, which is exponentially hard.

How does the covering number scales with dimensions and structures of policy class? It can go exponential in problem parameters, no? Where can we get a better polynomial type bounds on MDP parameters using this complexity measure? Also do we have to take the min over all base measures $\mu$? If yes, explain the intuition?

$C_{\mathrm{cov}}(\Pi)$ is the denotes the coverability of the policy class, i.e. the coverage of policies in $\Pi$ among all possible offline distributions $\mu$, hence in the formulation we have to take min over all base measures. This notion is very natural for measuring the complexity of $\Pi$, as it notes the minimal efforts for learning under the covariant shift of all policies in $\Pi$. When the state space and action space are discrete, this notion has another formulation that might be more intuitive:

$C_{\mathrm{cov}}(\Pi) = \max_{h} \sum_{s_h\in S_h, a_h\in A}\sup_{\pi\in \Pi} d^\pi(s_h, a_h).$

Here we briefly some common MDPs with bounded coverability guarantee:

• Tabular MDPs: $C_{\mathrm{cov}}(\Pi) \leq |S||A|$

• Block MDPs: $C_{\mathrm{cov}}(\Pi) \leq |S||A|$, where $S$ is the latent state space

• Linear/low-rank MDPs: $C_{\mathrm{cov}}(\Pi) \leq d|A|$, where $d$ is the feature dimension

• Sparse low-rank MDPs: $C_{\mathrm{cov}}(\Pi) \leq k|A|$, where $k$ is the sparsity level.

As shown by the above examples, the coverability coefficient scales polynomially with relevant problem parameters, instead of exponentially.

The formal proof for Theorem 3 of preference based optimization passes through proposition 22 and thus, proposition 8, which tries to control the Hellinger distance between the Bernoulli distributions over trajectories induced by different reward models. Why it has to be the Hellinger distance between them? Why not TV or any other metric? Can you explain this choice?

The main purpose of Proposition 8 is to provide non-asymptotic guarantees for maximum likelihood estimates (MLE). We choose the Hellinger distance primarily to facilitate the analysis, as it offers technical convenience in theoretical derivations. As the TV distance can be upper bounded by the Hellinger distance, Proposition 8 still holds if the Hellinger distance is replaced by TV distance. Our choice of formulation aims to maintain generality, extending the applicability of the results beyond the immediate scope of this paper.

We thank the reviewer for bringing the work of Kausik et al. (2024) to our attention. To facilitate a clear comparison, we outline the key distinctions between the two settings:

• Our setting (A): The outcome feedback is (a noisy observation of) the sum $R_1(s_1,a_1)+\cdots+R_H(s_H,a_H)$

• Setting of Kausik et al. (2024) (B): The outcome feedback is a (possibly sparse) vector $(R_h(s_h,u_h,a_h))_{h\in \mathcal{H}}$, where $u_h$ is the unobserved reward state that can depend on the history up to step $h$ in an arbitrary way.

We would like to note that setting (A) represents the most commonly studied outcome-reward model in recent theoretical works (Efroni et al., 2021; Pacchiano et al., 2021; Chatterji et al., 2021; Wu and Sun, 2023; Wang et al., 2023; Cassel et al., 2024; Lancewicki and Mansour, 2025). When we refer to providing a "comprehensive theoretical analysis of outcome-based online RL," we are specifically addressing this well-established setting (A).

We acknowledge that setting (B) presents greater learning challenges, as the reward structure may depend on the entire history. However, we would like to discuss some limitations when directly applying the results of Kausik et al. (2024) to our outcome feedback setting (A):

• Trajectory space complexity: The upper bounds in Kausik et al. (2024) scale with variants of the eluder dimension over the trajectory space, which must be $\Omega(|\mathcal{A}|^H)$ in worst-case scenarios (e.g., combination locks). The conditions under which trajectory eluder dimension can be bounded by other relevant problem parameters remain largely unexplored. Notably, it cannot be bounded by the per-step eluder dimension, as demonstrated by our lower bound. While such dependence on trajectory eluder dimension may be unavoidable under the fully general setting (B) due to combination locks falling into this category, we believe there is value in exploring more refined analyses for specific subclasses.

• One of our objectives is to avoid dependence on eluder dimension over trajectory space—an approach that aligns with recent advances in partially observable RL, which typically leverage specific structural properties (observability, decodability, stability, etc.) other than trajectory eluder dimension to obtain clearer bounds. We identify a broad and practically relevant class of MDPs that are learnable under setting (A), with upper bounds scaling with the coverability of the underlying MDP—a relatively intuitive and well-understood complexity measure.

• Importantly, coverability serves as an intrinsic complexity measure of the MDP structure and remains bounded even when the eluder dimension of the value function class becomes unbounded (as with neural networks).

While we recognize that setting (B) is indeed more general than (A), setting (A) remains significantly more challenging than learning with per-step (process) reward feedback. Previous works addressing setting (A) have primarily focused on linear rewards or functions with manageable trajectory eluder dimension. In this context, we believe our upper bounds using state-action coverability represent a meaningful theoretical contribution that involves several novel analytical techniques.

We are grateful for the reviewer's observation that the phrase "comprehensive theoretical analysis of outcome-based online RL" could be clearer. In our revision, we will explicitly highlight that: (1) this work specifically addresses "sum of rewards" outcome feedback, and (2) we will provide appropriate context regarding other more general outcome feedback models considered in related literature.

If the assumption that the outcome-based feedback is given by the sum of rewards is relaxed, how do you think the results would change?

When the outcome feedback takes the form of a general, non-linear function $R(s_1,a_1,\cdots,s_H,a_H)$, our upper bounds would indeed hold, but with coverability measured over the trajectory space rather than state-action space. However, trajectory coverability is typically much larger than standard coverability and, in worst-case scenarios, grows exponentially with the horizon—a highly undesirable property.

This exponential dependence appears to be fundamental rather than an artifact of our analysis. For example, for the threshold outcome model (which outputs 1 if the sum of rewards exceeds a fixed threshold and 0 otherwise), it is possible to embed any H-step combination lock into an H-step MDP with a single state (as demonstrated by Kausik et al., (2024)). This construction shows that any algorithm operating with only threshold feedback must incur an exponential sample complexity $\Omega(|\mathcal{A}|^H)$ in the worst case.

We hope this clarification helps position our work appropriately within the broader outcome-based RL literature, and we thank the reviewer again for this valuable feedback.

I thank the authors for the clarification. It does indeed help position this paper within the broader outcome-based RL literature. I have no further questions, but will defer any finalized any score adjustments to after discussion with the other reviewers.