acceptodds
Under review as a conference paper at ICLR 2027

Scalable and Efficient Learning Without Rewards in High Dimensional MDPs

Abstract

From its theoretical foundations to mathematical and scientific reasoning of frontier reasoning models, reinforcement learning has been the cornerstone of striking progress in learning complex policies directly from high-dimensional representations. Nonetheless, a significant limitation of reinforcement learning remains its reliance on a predefined, extrinsic reward signal, a foundational assumption that often fails when the computational cost of building a reward function exceeds that of learning the policy itself. In this paper, we investigate the problem of sequential decision-making in high-dimensional MDPs where reward information is absent. We introduce harmonic learning, a theoretically well-founded paradigm for learning in high dimensional MDPs where the explicit reward is not provided. By leveraging the uncertainty principle of harmonic analysis, our analysis and method provide a theoretical basis for effective and efficient learning with accelerated training. The theoretical and empirical analysis reported in our paper demonstrates that our method achieves substantially higher performance with significant efficiency, resulting in stable and resilient policies that can generalize to uncertain environments.

Primary area:
reinforcement learning
Keywords:
uncertainty principle, harmonic learning, high dimensional MDPs

Reviews

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

This paper studies RL for high-dimensional MDPs, in which explicit reward is not present. It claims to develop accelerated training using tools, more specifically the uncertainty principle from harmonic analysis. It provides theoretical and empirical results in support of its claims. More specifically, an algorithm is proposed that randomly removes some components. This is supposed to yield randomization, which is supposed to convert to a better sample complexity and robust policy. Main results are Propositions 3.3 and 3.5.

Critical strengths

This work does not seem to be strong. The theoretical results do not support the claims. The only silver lining seems to be that an attaempt is made to borrow tools from distant fields. The experimental results seem to show that the method is effective.

Critical weaknesses

Parts of the paper are quite wrong. Generally, the paper is not well-written and cryptic. I am highlighting some of the issues below:

  1. " a fundamental assumption persists in reinforcement learning: that the agent has direct access to the reward function of the MDP," --> not really. As long as some form of "noisy" and "partial information" about the rewards is revealed to the agent (this could be after some delay too), efficient learning can occur.

  2. " from bee foraging to human decision making, i"--> in all these cases there is some reward which is observed by the agent (this could be function also of the noise, in addition to state and actions).

  3. Explain the equation on Line 93. Additionally give some reference, or derive it. ("In settings where the state or action space have high-dimensional representations, the state-action value function is approximated via a deep neural network......").

  4. Several important works which use Linear programming approach to solve MDPs/RL, are missing.

  5. what exactly is meany by instability in the context of RL. E.g. explain in one paragrapg, or define this explicitly near "In this line of research some studies tried to further identify these instabilities".

  6. Definition 3.1 is not clear. Is the value function time-dependent? Is it episodic MDP (what is H??) ?

  7. The logic behind algorithm 1 is not clear. Take the simple case of 2 armed bandit. Algorithm 1 in this case eseentially sets to 0 the reward estimate of the arm that was selected in the current round. Since the estimate of the oher arm will be positive (with high probability), this essentially reduces to \epsilon_t exploration policy.

  8. Explain the stable basis assumption in more detail, and show what does it mean for the simplest of all settings (N-armed bandit or 2-armed bandit). It seems very restrictive.

  9. The results (Proposition 3.3, 3.5) do not say anything about the sample complexity, or regret , or the convergence rates. Hence, the claimed gains are not really proved.

  10. The experimental section is rather limited. It does not compare with the state-of-the-art policies.

Questions for authors
  1. Please explain the stable basis assumption in more detail, and show what does it mean for the simplest of all settings (N-armed bandit or 2-armed bandit). It seems very restrictive. Canyou please workout the calculations and show that this could hold in this case?

  2. Please show the working of the proposed algorithm for the finite-arms bandit case. If my understanding is correct, it reduces to the \epsilon exploration strategy.

  3. The main results (Proposition 3.3 amd 3.5) do not prove sample complexity or regret bounds. Hence, how does one judge the efficiency of the proposed algorithm?

2 comments
  1. ”Please explain the stable basis assumption in more detail, and show what does it mean for the simplest of all settings (N-armed bandit or 2-armed bandit). It seems very restrictive. Canyou please workout the calculations and show that this could hold in this case?”

The stable basis assumption is an assumption about properties of the space of features used by the value function. In particular, it only requires that the value function and state-action feature vectors are spread out with respect to the stable basis, as this is a standard feature with the Fourier basis or other Harmonic analytic bases. We now provide a fully worked out example for nn-armed bandits.

In the nn-armed bandit setting, let ϕk∈Rn\phi_k \in \mathbb{R}^n denote the feature vector corresponding to the kk-th arm, and let θ∈Rn\theta\in\mathbb{R}^n be the parameter vector of the optimal Q function. Let v1,…,vnv_1,\dots,v_n be an orthonormal basis. Then we can write each feature vector for the kk-th arm with coefficients cikc_{ik} from this basis i.e. ϕk=∑icikvi\phi_k = \sum_i c_{ik} v_i. We can similarly write the optimal parameter vector θ\theta with coefficients bikb_{ik} in this basis i.e. θ=∑ibikvi\theta = \sum_i b_{ik} v_i. Because the viv_i basis is orthonormal we have that the dot product which defines the Q-value of the kk-th arm is equal to Q(k)=ϕk⋅θ=∑icikbikQ(k) = \phi_k \cdot \theta = \sum_i c_{ik}b_{ik}. In this case, the viv_i form a stable basis if each term contributes approximately equally to the above sum. That is it means that cikbik≈ϵ1/nQ(k)c_{ik}b_{ik} \approx_{\epsilon} 1/n Q(k) where ≈ϵ\approx_{\epsilon} means that the two sides of the equation are within ϵ\epsilon of each other.

For a simple example, let viv_i be the Hadamard basis in Rn\mathbb{R}^n. This is an orthornormal basis where every coordinate of each viv_i is either 1/n1/\sqrt{n} or −1/n-1/\sqrt{n}. Next, let the feature vectors for arm kk be the Euclidean standard basis vectors ϕk=ek\phi_k = e_k. Similarly, let θ\theta be an ss-sparse vector which has only s<ns < n non-zero coordinates, each of which is equal to 1. Hence, Q(k)=1Q(k) = 1 for ss of the arms, and Q(k)=0Q(k) = 0 for the rest. Further, the bounded coordinates of the Hadamard basis guarantee that ∣cik∣≤1/n|c_{ik}|\leq 1/\sqrt{n} and ∣bik∣≤sn|b_{ik}| \leq \frac{s}{\sqrt{n}}. Hence, for each term we have ∣cikbik∣<s/n|c_{ik}b_{ik}| < s/n. If we let ϵ=s/n\epsilon = s/n then our condition of a stable basis is satisfied both when Q(k)=1Q(k) = 1 (because 1/n1/n is within ϵ\epsilon of s/ns/n) and when Q(k)=0Q(k) = 0 (because 1/n⋅0=01/n \cdot 0 =0 is within ϵ\epsilon of s/ns/n).

  1. ”Please show the working of the proposed algorithm for the finite-arms bandit case. If my understanding is correct, it reduces to the \epsilon exploration strategy.”

This understanding is not correct, the definition of a stable basis depends on the feature representation chosen for each state-action pair. For finite-armed bandits, the working of the algorithm is completely dependent on the feature representation, and does not reduce to ϵ\epsilon-greedy exploration. Take the example described above for instance. In that case, the algorithm adds noise by dropping a single Hadamard basis vector. Each time an arm kk is selected, and we update the estimated value function, the estimated value of Q(k)Q(k) gets closer to the true value. Now because the Hadamard basis is a stable basis, we know that the true QQ-function changes very little when we drop a single Hadamard basis vector. Thus, the noise added to Q(k)Q(k) decreases as arm kk is visited more often and the value of Q(k)Q(k) gets more accurate. That is: the value function exploration noise is automatically decreased for arms that are closer to optimal, while it remains larger for arms that have not yet been accurately estimated.

  1. ”The main results (Proposition 3.3 amd 3.5) do not prove sample complexity or regret bounds. Hence, how does one judge the efficiency of the proposed algorithm?”

The goal of this paper is to introduce a theoretically grounded learning paradigm that could be immediately applied to more general settings. Our method indeed has a strong theoretical motivation which suggests using the Fourier basis as a stable basis, and our empirical analysis shows that our algorithm learns substantially high performing policies in high-dimensional MDPs with neural-network function approximators.

  1. ”Definition 3.1 is not clear. Is the value function time-dependent? Is it episodic MDP (what is H??) ?”

Yes, Definition 3.1 is in the setting of an episodic, finite horizon MDP with horizon HH. This setting was chosen as it is the same as the prior theoretical work on value function randomization. There, purely for generality, the value function is allowed to be time dependent. Of course, this analysis can equally well be specialized to the time-invariant value function setting.

Reviewer_Y3KWOpenReview ↗

Response read

I thank the authors for their effort in responding to my concerns. However, these are not satisfactory, and did not address my concerns. Though this does improve the standing of the paper, its not enough in order for the score to be changed. Consequently, I would stick to my score.

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

The paper proposes Harmonic Learning, a method for learning from expert demonstrations without using environment rewards during training. It modifies image observations by randomly masking Fourier frequency components and then reconstructing the images for IQ-Learn. The authors introduce a stable-basis analysis to motivate this approach and a frequency-based robustness test called SBRA. Experiments on five Atari games report improved returns and robustness to visual changes.

Critical strengths

1.The method adds frequency-domain processing to IQ-Learn without introducing an additional trainable model or adversarial optimization. This simplicity makes it a practical approach to improving visual imitation learning.

2.The paper introduces SBRA, which measures how policy performance changes when different image-frequency components are removed. This provides a clear way to identify which frequencies a policy is sensitive to. Beyond the training method itself, this diagnostic tool is useful for understanding a policy’s dependence on visual information rather than judging it only by its overall task score.

Critical weaknesses

Critical Weaknesses

1. The evidence does not clearly establish the benefit of the specific harmonic design. Proposition 3.3 analyzes removing a single basis component under linear function approximation, while the actual method masks groups of Fourier coefficients and uses a deep Q-network. SBRA provides empirical evidence of frequency sensitivity, but does not directly establish that Atari observations satisfy the stated stable-basis conditions. The connection between the theory and the implemented method therefore remains unclear.

Also, Reinforcement Learning with Augmented Data (RAD) [1] has shown that simple image augmentations can improve visual RL. A controlled comparison between Harmonic Learning and task-appropriate RAD-style augmentations within the same IQ-Learn framework is missing. Without this comparison, it is difficult to tell whether the gains come from the specific harmonic mechanism or more general observation perturbation. This limits my confidence in the method’s distinct contribution.

2. The experimental evidence is limited for the sample-efficiency and generality claims. The main results cover only five Atari games, and I could not find full learning curves showing evaluation return against environment interactions. The reported scores and the Pong comparison of 50K versus 1M interactions do not show how consistently the method learns faster across games, or how the performance gap changes with further training. Broader task coverage and complete learning curves would be important for assessing the claimed sample-efficiency gains and applicability beyond the selected tasks.

References

[1] Misha Laskin, Kimin Lee, Adam Stooke, Lerrel Pinto, Pieter Abbeel, and Aravind Srinivas. Reinforcement Learning with Augmented Data. In Advances in Neural Information Processing Systems, volume 33, 2020.

Questions for authors
  1. Why were these five Atari games selected? Do you have results on other games or environments showing that the improvements are not limited to these tasks?
  2. Can you provide curves showing game scores against the number of environment interactions, including variation across runs?
  3. What evidence shows that Atari images satisfy your Stable Basis assumptions when represented in the Fourier basis?
  4. Can you compared Harmonic Learning with simple image augmentations, such as cropping or shifting used in RAD, under the same IQ-Learn framework, expert data, and training budget? This comparison would help show whether your specific frequency-based method offers benefits beyond ordinary data augmentation.
1 comment

We are glad to see that you found that our paper provides a clear way to identify which frequencies a policy is sensitive to and that beyond introducing the training method itself, our diagnostic tool is useful for understanding a policy’s dependence on visual information rather than judging it only by its overall task score. We also highly appreciate you highlighting how our method improves the performance without introducing computational complexity, and further emphasizing the simplicity and the practicality of our method.

  1. ”Why were these five Atari games selected? Do you have results on other games or environments showing that the improvements are not limited to these tasks?”

We strictly followed the exact experimental benchmark of prior work, and the exact same games were used as in prior work to ensure that a direct, transparent, and fair comparison is provided.

  1. ”What evidence shows that Atari images satisfy your Stable Basis assumptions when represented in the Fourier basis?”

We provide both theoretical and direct empirical evidence in Section 3.1 and Section 4.1 showing that Atari state observations satisfy the ϵ\epsilon-stable basis condition (Definitions 3.1 and 3.4) in the Fourier basis. First, In Section 3.1, we prove in Proposition 3.5 that in the general function approximation setting, one can directly test for the presence of an ϵ\epsilon-stable basis by deleting random basis components s~=s−(vi⊤s)vi\tilde{s} = s - (v_i^\top s)v_i and verifying that the expected cumulative rewards RR under the optimal policy remain invariant (R=R∗R = R^*). Second, we provide direct empirical evidence in Section 4.1. As shown in Figure 2 (blue curve), when individual frequency bands δ\delta of the Fourier transform are removed from Atari state observations, a converged vanilla Deep RL policy experiences near-zero, uniform performance impact (I≈0.00 to 0.02\mathcal{I} \approx 0.00 \text{ to } 0.02) across the entire frequency spectrum. As explicitly noted in lines 300–304 and 353–356, this flat sensitivity profile empirically verifies that the converged optimal value function satisfies the ϵ\epsilon-stable basis condition ∣1κΦt(s,a)⊤θt∗−Φ^t(s,a)ivi⊤θt∗∣<ϵ\vert{}\frac{1}{\kappa}\Phi_t(s,a)^\top \theta_t^* - \hat{\Phi}_t(s,a)_i v_i^\top \theta_t^*\vert{} < \epsilon with respect to the Fourier basis in Atari.

  1. ”Can you compared Harmonic Learning with simple image augmentations, such as cropping or shifting used in RAD, under the same IQ-Learn framework, expert data, and training budget? This comparison would help show whether your specific frequency-based method offers benefits beyond ordinary data augmentation.”

Harmonic Learning is a theoretically grounded value-function randomization mechanism rather than heuristic data augmentations such as RAD. As proven in Proposition 3.3, randomly eliminating an ϵ\epsilon-stable harmonic basis element injects noise into the Q-function with variance strictly equal to the parameter uncertainty (Var[η]=Υθt(s,a)\text{Var}[\eta] = \Upsilon_{\theta_t}(s,a)), directly transferring the provable sample-efficiency mechanism of RLSVI to general function approximation. Furthermore, as also discussed in lines 281–286, by the uncertainty principle of harmonic analysis, removing a single Fourier component spreads the perturbation globally without altering the localized spatial semantics or optimal action of the state. In contrast, cropping or shifting alters pixel coordinates and heuristically removes the localized game-critical semantics and objects without any theoretical grounding, corrupting the state-action correspondence required in Inverse Q-Learning while failing to address the frequency-domain sensitivities identified in our Stable Basis Robustness Analysis (Figure 2, Section 4.1).

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

This paper is about seqencial decisional-making in high-dim Markov decision processes (MDPs).

The crucial part of the setting is that the explicit reward is not provided.

Theoretical findings are provided.

Empirical analysis is supporting the theoretical findings.

Critical strengths

Line 276 of the text clearly highlights some crucial discussions.

The research question is quite crucial.

Critical weaknesses

Regarding the ALE (Arcade Learning Environment), it appears to be a relatively older environment and baseline for current research. Do you think there are any reference, literature, or ongoing discussions regarding newer, more challenging benchmark environments that are more representative of modern advancements?

Questions for authors

With how far AI agents have come recently, is Line 112 stability still a problem worth worrying about? Most of the references in this part look like from a few years back, though one is mostly recent. Do you think has it essentially been fixed by newer updates?

It seems that the appendix can be attached to the paper.

I'm curious about the conceptual intuition behind the word harmonic. Where does the name come from, and what is its fundamental relationship to mathematical concepts like series, means, or functions?

2 comments

We are glad to hear that you found that our paper addresses a crucial research question and introduces a theoretically founded method where our empirical analysis verifies the theoretical predictions. We also truly appreciate you valuing the presentation, quality and soundness of our paper highly.

  1. ”Regarding the ALE (Arcade Learning Environment), it appears to be a relatively older environment and baseline for current research. Do you think there are any reference, literature, or ongoing discussions regarding newer, more challenging benchmark environments that are more representative of modern advancements?”

Thank you for this question. ALE is still the standard benchmark in deep reinforcement learning algorithmic developments [1,2,3,4,5,6].

[1] Scalable Reinforcement Learning via Adaptive Batch Scaling, ICML 2026.

[2] Counteractive RL: Rethinking Core Principles for Efficient and Scalable Deep Reinforcement Learning, NeurIPS 2025. [Spotlight Presentation]

[3] Reinforcement Learning with Discrete Diffusion Policies for Combinatorial Action Spaces, ICML 2026.

[4] Underlying Functional Structure of Reinforcement Learning, NeurIPS 2026.

[5] Read and Reap the Rewards: Learning to Play Atari with the Help of Instruction Manuals, NeurIPS 2026.

[6] Local Reinforcement Learning with Action-Conditioned Root Mean Squared Q-Functions, ICLR 2026.

  1. “With how far AI agents have come recently, is Line 112 stability still a problem worth worrying about? Most of the references in this part look like from a few years back, though one is mostly recent. Do you think has it essentially been fixed by newer updates?”

Thank you for this insightful question. The robustness issues of reinforcement learning are unfortunately still an unresolved issue. Specifically, the methods that have been proposed to robustify these models have been shown to be vulnerable to black-box attacks which are still not resolved, it has been demonstrated that these models are unable to generalize as much as the standard models and furthermore, the recent studies further show that the robustification efforts make these models lose their reasoning capacity.

  1. ”I'm curious about the conceptual intuition behind the word harmonic. Where does the name come from, and what is its fundamental relationship to mathematical concepts like series, means, or functions?”

Thank you for this question. In our work, we call our paradigm Harmonic Learning because it directly operates in the harmonic analytic (Fourier) basis of high-dimensional state observations. As also discussed in Section 3 between lines 276–295, our method leverages the uncertainty principle of the Fourier transform, which states that a signal localized in the spatial/standard basis must be spread out across the harmonic (frequency) basis. Historically and mathematically, this terminology stems from decomposing functions into orthogonal sinusoidal waves, i.e. Fourier series of harmonics, where wavelengths follow the harmonic mean/series, rather than direct use of the arithmetic harmonic mean.

Thanks for addressing the questions. I have read responses and reviews.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.