acceptodds
Under review as a conference paper at ICLR 2027

Rapid Mixing Is Not Enough: Hardness of Action-Conditioned Predictive Representation Optimization

Abstract

Action-conditioned self-prediction learns shared state representations for reinforcement learning by predicting future representations under different actions. However, existing spectral solutions for the associated tabular objective rely on a common eigenbasis, leaving the complexity of global optimization beyond this setting unresolved. We study this question for centered and whitened representations in finite state spaces, removing the constant component and normalizing feature covariance. We prove worst-case computational hardness of approximating the optimal objective value to inverse polynomial additive accuracy, even for strictly positive, symmetric transition kernels that mix rapidly and retain fixed signal strength after centering. Our construction embeds a hard graph problem into valid transition kernels, and a further reduction extends the hardness to every fixed representation dimension. For symmetric kernels, we give exact solutions when they commute and efficient additive approximation for a single feature when the centered operators span a space of fixed dimension. The hard instances also admit exact realizations as finite transition datasets. For the scalar empirical cross-covariance objective, polynomially many independent stationary samples preserve the hardness gap with high probability, even when centering, whitening, and representation selection use the same data.

Primary area:
learning theory
Keywords:
action-conditioned self-prediction, representation learning, computational complexity, hardness of approximation, Markov chains, reinforcement learning

Reviews

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

I have to honestly admit that my knowledge is not sufficient enough for reviewing the paper so my review should be taken lightly.

Overall, This paper studies the difficulty of optimizing action-conditioned prediction with shared representations in reinforcement learning. The paper proposes that rapid mixing does not directly lead to easy optimization, and more importantly, the structure of actions is more important and can be directly used for optimization. It additionally provides exact solutions under a common eigenbasis, an approximation algorithm for scalar representations with fixed effective action rank, and connections to finite transition datasets. The authors also provide a few experiments to validate the theoretical results.

Critical strengths
  • The paper clearly distinguishes favorable properties of individual transition kernels from the difficulty of globally optimizing a representation that can be shared across actions. The motivation is strong and lead to an important research problem.

  • The hardness result holds under meaningful restrictions, including positivity, symmetry, and a constant spectral gap. Thus, the mathematical derivation is solid and (from my limited knowledge) is correct.

  • The structural tractability results and finite-data analysis provide useful complements to the theoretical result.

Critical weaknesses
  • The experiments mainly illustrate the theoretical constructions and structural regimes. Some optimize the equivalent simplex objective, while some operator experiments do not impose stochasticity. Therefore, it would be interpreted as numerical illustrations, rather than general evidence of difficulty in practical predictive representation learning. The O(N9)O(N^9) sufficient sampling bound is also primarily of theoretical interest.
Questions for authors
  • As the authors pointing out that the difficulty is related to the effective rank and graph structure, a controlled experiment relate approximate effective action rank to the difficulty of optimizing the shared encoder can be meaningful.
  • In order to make sure the the optimization can directly minimize empirical prediction loss, what additional conditions would be needed for sampled guarantee?
4 comments
AuthorsOpenReview ↗

Author Repsonse

We thank the reviewer for their attention and reading of our paper. Below we try to address the concerns you raised.

Q1/W1. a controlled experiment relate approximate effective action rank to the difficulty of optimizing the shared encoder can be meaningful.

Following your suggestion, we added a controlled study of the relation between approximate action structure and encoder optimization. All transition kernels are strictly positive, symmetric, and stochastic. Riemannian ascent and SLSQP directly optimize the full scalar encoder in the original state coordinates.

Each kernel family has eight states and eight actions. We vary the span of a supplied operator approximation over r∈{1,2,4}r\in\{1,2,4\} and its average operator norm residual over η/β∈{0,0.05,0.15,0.30}\eta/\beta\in\{0,0.05,0.15,0.30\}, with β=1/4\beta=1/4. The centered operator norms remain close to β\beta, and the absolute spectral gaps are at least 3/43/4. For positive residuals, the full action span is six, while the prescribed approximation has span rr. Twenty base environments across these twelve conditions give 240 kernel families, with matched initializations across conditions.

The table reports the percentage of runs attaining a certified optimization gap of at most 6.25×10−56.25\times10^{-5}, with up to 2,000 sweeps per run. Each cell gives Riemannian ascent / SLSQP and summarizes 200 runs from 20 base environments with ten initializations each. Success is determined using verified bounds on the global optimum.

Approximation span rrη/β=0\quad\eta/\beta=00.05\qquad0.050.15\qquad0.150.30\qquad0.30
168.5% / 68.5%69.0% / 69.0%66.0% / 67.0%65.0% / 66.0%
261.5% / 62.5%58.5% / 58.5%59.0% / 59.0%67.0% / 67.5%
462.0% / 62.0%62.0% / 62.0%64.0% / 64.0%62.0% / 62.5%

Averaged across the four residual levels, the r=1r=1 group had the highest success rate per run for both methods. For r=1,2,4r=1,2,4, the rates were 67.1%, 61.5%, and 62.5% for Riemannian ascent, and 67.6%, 61.9%, and 62.6% for SLSQP.

Initialization also mattered. Riemannian ascent and SLSQP succeeded on 157/240157/240 and 159/240159/240 families from the first start, respectively, while selecting the best of ten starts increased both to 240/240240/240. As detailed in our response to Reviewer Huje, W2, strict suboptimal local maxima explain the failed runs in the exact rank-one subset. These results show that even when the global value is spectrally computable, local encoder optimization can depend on initialization and benefit from multiple starts. We also directly optimize the encoder on sparse Markov kernels with 1616 or 6464 states. The results are given in our response to Reviewer Huje, W3(ii).

W2. The O(N9)O(N^9) sufficient sampling bound is also primarily of theoretical interest.

We understand the reviewer's concern about the size of this sufficient bound. Actually, the N9N^9 sample bound in Theorem 4 allows us to control sampling error uniformly over encoders, keeping it small enough to preserve the population hardness gap in the sampled objective. A more refined analysis may reduce this sufficient sample bound. However, we note that our value approximation algorithms take explicitly given transition kernels as input. Their running time and accuracy guarantees would remain unchanged under such an improvement.

AuthorsOpenReview ↗

Author Repsonse Part 2

Q2. In order to make sure the the optimization can directly minimize empirical prediction loss, what additional conditions would be needed for sampled guarantee?

Our original Theorem 4 gives a sufficient sample size for preserving the hardness gap in the scalar empirical cross moment objective under independent stationary sampling. We have extended this analysis to fitted empirical prediction loss. Under explicit conditions on each action's empirical state marginals, we bound the excess empirical prediction loss of an encoder selected by optimizing the sampled objective (Appendix B.4). Here is our proof sketch.

Proof sketch. Let p^a\widehat p_a and r^a\widehat r_a be the empirical source and target state distributions for action aa, and let π^=m−1∑ap^a\widehat\pi=m^{-1}\sum_a\widehat p_a be the pooled source distribution. We use scalar features centered and normalized under π^\widehat\pi, with linear prediction heads without intercepts. Suppose π^i>0\widehat\pi_i>0 for every state and

\le\alpha_s<1,\qquad \max_{a,i}\left|\frac{\widehat r_{a,i}}{\widehat\pi_i}-1\right| \le\alpha_t.$$ Here $\alpha_s,\alpha_t\ge0$ measure the relative discrepancies of the action marginals. Write $G_a,Q_a,C_a$ for the empirical source second moment, target second moment, and cross moment of a feature $h$. The marginal bounds imply $|G_a-1|\le\alpha_s$ and $|Q_a-1|\le\alpha_t$ uniformly over all normalized features. In particular, $G_a>0$. Minimizing over each linear head gives $$\widehat L(h)=\frac1m\sum_a\left(Q_a-\frac{C_a^2}{G_a}\right), \qquad \widehat f(h)=\frac1m\sum_a C_a^2.$$ The empirical Cauchy-Schwarz inequality gives $C_a^2\le G_aQ_a$, so $$\left|Q_a-\frac{C_a^2}{G_a}-(1-C_a^2)\right| \le |Q_a-1|+|G_a-1|Q_a \le B:=\alpha_t+(1+\alpha_t)\alpha_s.$$ Averaging over actions yields \$ \left|\widehat L(h)-(1-\widehat f(h))\right|\le B \$ simultaneously for all feasible encoders. Consequently, any encoder $\widetilde h$ satisfying $\widehat f(\widetilde h)\ge\max_h\widehat f(h)-\varepsilon$ obeys \$ \widehat L(\widetilde h)-\min_h\widehat L(h) \le\varepsilon+2B. \$ Exact marginal balance gives $B=0$ and makes the two optimization problems equivalent. For approximate balance, the bound quantifies the additional prediction loss. Uniformity allows normalization, encoder selection, and predictor fitting to use the same samples. Under independent stationary sampling, concentration of the action marginals and the original objective comparison give a joint guarantee. For the Walsh construction with $N$ graph vertices and $m$ actions, $L\ge C N^9\log(8mN/\delta)$ samples per action suffice for $$\left|\min_h\widehat L(h)-(1-J)\right| \le\frac1{32N^4}$$ with probability at least $1-\delta$, where $C$ is a universal constant and $1-J$ is the minimum population prediction loss. An additional value approximation error of $1/(64N^4)$ still separates the two clique cases, extending the sampled hardness gap to fitted empirical prediction loss.

Dear Reviewer bsNt,

We are writing to ask whether our rebuttal has addressed your concerns. We would be happy to discuss any remaining issues.

I thank the authors for their rebuttal. The authors have sufficiently addressed my concern, so I would remain positive about this paper.

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

The paper studies self-predictive representation learning objectives, looking at action-conditioned problems where previous analysis required all action transition matrices to have a shared eigenbasis. This work aims to characterize the hardness of learning a representation which maximizes next-state similarity by reformulating a known NP-hard graph problem as an MDP. The main crux of the paper is to use a known hard task of finding a shared eigenbasis between matrices, converting the Walsh matrices into a reinforcement learning environment, and interpolating them with the all-ones matrix to guarantee arbitrarily rapid mixing. The empirical results show that despite the theoretical hardness of the problem Riemannian gradient descent rapidly converges to an optimal solution in the studied settings.

Critical strengths

Strengths:

  • I didn’t notice any obvious errors in the proofs
  • The paper address an open question from previous works by considering MDPs where action transition matrices do not share an eigenbasis, and constructs a nice counterexample by bridging tools from graph theory.
  • In particular, it is interesting to identify MDPs where mixing is rapid but in contrast the representation-learning problem is computationally hard, and to note that much of the hardness boils down to finding a good joint representation space across the different action matrices.
  • The paper shows that if the action rank is low, representation learning can be fast. This is not surprising but nice to have characterized.
Critical weaknesses

Weaknesses:

  • The paper’s technical contribution mostly boils down to taking a known hard family to the problem of finding a shared eigenbasis between matrices, applying an affine transformation to the family’s matrices so that they have a Markov chain structure, and then pointing out that finding the shared basis of this transformed set of matrices is still hard. While that is
  • There is also some tension between the hardness claims in the theoretical section and the apparent ease with which Riemannian gradient ascent converges to the correct solution in the empirical evaluations.
  • It’s not clear what the fact that finding a shared eigenbasis between some families of matrices is hard actually tells us about how representation-learning might go in practice. The hard family is not a `typical’ transition matrix (which in most RL environments are extremely sparse), and it’s not clear from the paper what properties of realistic environments would lead to similar difficulty of representation learning.
Questions for authors

Can the authors share whether there are insights from these results about what properties will in general make representation learning easy or hard given a set of action transition matrices?

6 comments
AuthorsOpenReview ↗

Author Repsonse

We thank the reviewer for their careful and detailed review of our work that helped us significantly improve it. Below we hope to address some of your concerns.

W1. The main technical contributions seem to be limited.

We understand the reviewer's concern about the paper's contribution, but would like to clarify a possible misunderstanding. We study approximation of the globally optimal shared prediction value, whereas the review describes the task as finding a common eigenbasis. Our formulation addresses shared predictive representation learning for a broader class of action dynamics, including kernels that have no common eigenbasis and therefore cannot be simultaneously diagonalized. Furthermore, here are some important and original insights you may find of interest.

(i) A hard shared prediction problem can be built from actions with identical, simple spectra. Every centered action operator in our scalar construction has rank two and eigenvalues ±1/4\pm1/4. The graph is encoded in which pairs of directions the actions couple. Our Walsh embedding spreads these couplings across states, keeping transition probabilities positive and the absolute spectral gap fixed at 3/43/4. The joint prediction optimum remains NP-hard to approximate at the stated inverse polynomial accuracy (Proposition 1; Theorem 2). This shows how the interactions between actions can carry computational difficulty that their individual spectra and mixing rates do not reveal.

(ii) We can use repeated prediction tasks to determine how an optimal representation allocates its dimensions. For any fixed dd, we introduce anchor actions whose total weight makes losing an anchor more costly than any gain from reallocating that capacity to the graph. Every optimal representation must consequently devote d−1d-1 dimensions to the anchor subspace, leaving one feature direction for the scalar hard instance. The prediction objective itself enforces this allocation, even though the encoder is free to choose its full representation subspace. This is the mechanism that carries hardness to every fixed representation dimension (Corollary 3).

(iii) Scalar optimization can be tractable even when the actions have no common eigenbasis. Our algorithm moves the nonlinear search from the space of state features to linear combinations of action operators. For each combination, a largest eigenvalue calculation on the centered subspace solves the inner optimization. Only r=dim⁡span⁡{B1,…,Bm}r=\dim\operatorname{span}\{B_1,\ldots,B_m\} independent coefficient directions need to be searched, so the exponential cost depends on rr, while the dependence on the state count remains polynomial. This gives a route to efficient value approximation for fixed rr that also covers noncommuting kernels (Theorem 6).

W2. Why does optimization appear easy despite the hardness result?

These observations do not contradict our hardness result. A worst-case complexity lower bound does not imply that local optimization must be difficult on every instance.

The original Figure 22(a,b) measures recovery of the ordering between adjacent clique levels. To examine attainment of the global optimum directly in the encoder coordinates, we added experiments on 240240 families of valid Markov kernels with eight states and eight actions. The table reports certified successes at additive tolerance 6.25×10−56.25\times10^{-5}, with up to 2 0002\,000 sweeps per start.

\qquad MethodFirst startBest of ten starts
Riemannian ascent157/240157/240240/240240/240
SLSQP159/240159/240240/240240/240

Success was determined using verified bounds on the global optimum. Multiple starts attained the target accuracy on every family, while a single start could terminate at a suboptimal solution. This supports the effectiveness of restarts on these instances and shows why initialization matters when interpreting the apparent ease of local optimization.

This initialization sensitivity has a concrete explanation even in a spectrally solvable subset. When the centered actions span one dimension, the objective is a squared Rayleigh quotient. Spectral extremes of opposite signs can both be local maxima, with the smaller magnitude yielding a suboptimal value. We verified strict suboptimal maxima in 1818 of the 2020 such families. The failed runs in this subset attained objective values agreeing with these extrema to numerical precision. Thus, global tractability can coexist with local optimization failures.

AuthorsOpenReview ↗

Author Repsonse Part 2

W3. (i) What do the hardness results imply for representation learning in practice, (ii) do they extend to sparse transitions, and (iii) which properties of realistic environments can lead to similar difficulty?

(i) Optimizing our shared prediction objective can improve the downstream predictive performance of learned representations. We show that a smaller latent optimization gap yields a tighter upper bound on excess external prediction error, and our added experiments show lower mean prediction error on all four external targets relative to matched random initial encoders (our reply to Reviewer L2Lx, Q2/W3).

(ii) We agree that transition matrices in many RL environments are extremely sparse. Our original construction uses dense kernels, which limited its direct applicability to this setting. We have extended the hardness analysis to sparse kernels for the same one-step scalar prediction objective. We prove that approximating its globally optimal value at inverse polynomial additive accuracy is NP-hard even when every action kernel has at most ten nonzero entries per row (Appendix D.2). Here is the proof sketch.

Proof sketch. Start with a graph GG with NN vertices and m≥1m\ge1 edges, and pad it to q=2⌈log⁡2N⌉q=2^{\lceil\log_2N\rceil} vertices. We construct kernels on two copies of these vertices using a graph edge, a matching, and a small cycle component for each action. Each state can reach its own vertex, its matching partner, at most one graph neighbor, and two cycle neighbors, in either layer. This gives at most ten nonzero entries per row. The kernels are rational, symmetric, and stochastic, and the cycle component ensures irreducibility and positive diagonals.

The kernels preserve the symmetric and antisymmetric layer subspaces. We choose the perturbation weights so that averaging over the matchings gives a strict separation J−>J+J_->J_+ between the maximum objective values on the antisymmetric and centered symmetric subspaces. For any centered unit encoder xx, let pp be its squared norm in the antisymmetric subspace. Convexity of the square gives F(x)≤pJ−+(1−p)J+≤J−F(x)\le pJ_-+(1-p)J_+\le J_-.

Every global maximizer therefore lies in the antisymmetric subspace and has the form x=(z,−z)/2x=(z,-z)/\sqrt2 with ∥z∥=1\|z\|=1. Within this subspace, pairing actions with opposite edge perturbations cancels the linear terms and leaves the graph quartic used in Theorem 2. The identity of Motzkin and Straus then gives

=B+C\max_{\|z\|=1}\sum_{\{i,j\}\in E(G)}z_i^2z_j^2 =B+\frac C2\left(1-\frac1{\omega(G)}\right).$$ Here $B$ and $C>0$ are explicitly known rational quantities, $C=\Theta(1/(mq^4))$, and $\omega(G)$ is the clique number. Consecutive clique sizes give values separated by $\Omega(q^{-8})$, so sufficiently small inverse polynomial additive error distinguishes the CLIQUE instances. The kernels and thresholds are constructed in polynomial time. This establishes hardness over the full domain of centered unit encoders for sparse kernels whose absolute spectral gaps tend to zero with the state count. Thus, a bounded number of successors per state and action is insufficient to guarantee efficient global optimization at inverse polynomial additive accuracy. We also added experiments on periodic grids and mixtures of regular graphs, with 16 or 64 states and four actions. Each kernel combines shared base dynamics with dynamics specific to that action, whose weight is varied over $\alpha\in\{0,0.1,0.5\}$. This ranges from identical actions to distinct action dynamics while preserving sparse transitions. Using 20 base seeds across the two topologies, two sizes, and three weights gives 240 kernel families. We directly optimized the full scalar encoder using Riemannian ascent and SLSQP. With one initialization and a budget of at most 2,000 sweeps, each method achieved certified additive error at most $0.01$ on all 240 families. A spectral candidate achieved the same accuracy. This provides direct evidence that the objective can be successfully optimized on these sparse environments across the tested variations in action dynamics. ***(iii)*** Two properties jointly yield the difficulty: 1. Different actions induce different couplings among overlapping state features. 2. The number of independent action effects grows with the environment's size. When the encoder has limited capacity, the first property can make the features useful under different actions compete for that capacity. The second property increases the number of distinct transition patterns that the shared representation must accommodate. Our hard family captures this combination explicitly. Each action couples a pair of feature directions, and these pairs overlap according to the edges of a graph. We construct the couplings so that approximating the best shared prediction value at the accuracy in Theorem 2 determines the graph's clique number. This explains how individually simple action dynamics can give rise to a difficult joint representation problem.
AuthorsOpenReview ↗

Author Repsonse Part 3

Q1. What properties will in general make representation learning easy or hard given a set of action transition matrices?

This is a good question. Our results identify two structural properties that help explain what makes representation learning easy:

  1. The alignment of predictive directions across actions. When the symmetric action operators share a common eigenbasis, the same feature directions remain invariant under every action. Their contributions to the shared prediction objective can then be evaluated separately, using each centered direction's mean squared eigenvalue across actions. A common eigenbasis therefore makes representation learning tractable through spectral selection of the dd centered directions with the highest scores, which gives an encoder attaining the minimum prediction loss (Theorem 5).

  2. The number of independent components in the action dynamics. Many actions can be different mixtures of the same two symmetric transition kernels, in which case their centered operators span at most two dimensions. More generally, Theorem 6 shows that, for scalar representations, a fixed dimension of this span permits polynomial time approximation of the globally optimal value JJ, even at inverse polynomial additive accuracy. Since the minimum fitted scalar prediction loss is 1−J1-J, a fixed number of independent dynamics components makes the best prediction performance attainable by a scalar encoder efficiently approximable, even when there are many actions.

Representation learning can become hard when different actions favor different combinations of features, and a shared encoder must decide how to allocate its limited capacity across them. Our Theorem 2 construction captures this joint selection problem by assigning overlapping pairs of feature directions to actions according to the edges of a graph. A normalized scalar encoder must allocate its squared norm across the directions, so changing the weight on one direction affects several actions at once. We construct these couplings so that the globally optimal prediction value encodes the graph's clique number, making approximation NP-hard at the accuracy in Theorem 2. Each individual kernel still mixes rapidly and has a centered operator of rank two. The difficulty in this family comes from choosing how one shared encoder allocates its representation capacity across these coupled action effects.

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

The paper investigates the computational complexity of learning a shared state representation whose next-step features can be predicted linearly from the current features and the action. Prediction takes place entirely in the latent space. The representation is centered and whitened to exclude constant features and prevent collapse. Under symmetric transition kernels with a common uniform stationary distribution, eliminating the action-specific linear predictors reduces the problem to maximizing the average squared feature cross-covariance across actions. Section 3 establishes worst-case computational hardness of optimizing the shared predictive representation. A reduction from maximum clique shows that approximating the optimal objective value to inverse-polynomial additive accuracy is NP-hard, even for strictly positive, symmetric, rapidly mixing kernels and any fixed representation dimension. The construction also yields exact finite datasets with the same hardness, while sufficiently many independent stationary samples preserve the hardness gap with high probability for the scalar empirical cross-covariance objective. Section 4 identifies two tractable cases. For symmetric kernels that commute pairwise, the optimal representation is obtained by selecting common nonconstant eigenvectors with the largest average squared eigenvalues, yielding an exact spectral characterization. For a single feature, the authors also provide an additive approximation algorithm whose runtime is exponential in the dimension of the span of the centered action operators, but polynomial for fixed span dimension. Section 5 uses synthetic experiments to illustrate recovery of graph-dependent signals from finite trajectories, the limitations of generic optimizers under fixed computational budgets, and the benefit of spectral optimization when kernels share an eigenbasis. These experiments support the theoretical analysis but do not evaluate downstream RL performance.

Critical strengths

• The paper addresses a clear theoretical question: whether a single predictive representation can be optimized efficiently across several action-dependent transition operators. It shows that favorable properties of individual operators do not suffice to make their joint optimization tractable. • The paper complements its negative results with an exact spectral characterization for commuting kernels and an approximation algorithm for a single feature when the centered action operators span a fixed-dimensional space. This helps identify which forms of shared structure can make optimization manageable.

Critical weaknesses

• The result concerns approximation to a specified inverse-polynomial additive accuracy, rather than constant-error approximation or the quality of practically useful representations. Moreover, the hard construction has a growing number of independent action operators. It therefore leaves open how difficult the problem is at realistic tolerances and with small action spaces. • The analysis imposes exact centering and whitening constraints. It is not established whether comparable hardness holds for soft penalties, approximate normalization, or other mechanisms used to prevent representation collapse. The paper would benefit from explaining how its constrained objective relates to practical predictive representation learning and which aspects of the hardness survive changes in formulation. • The objective measures linear predictability entirely within the learned feature space. It does not require preservation of rewards, reconstruction of transition dynamics, or good control performance. Consequently, hardness of globally optimizing this objective does not directly establish difficulty in learning representations that are useful for reinforcement learning. • The paper moves quickly from the predictive-learning motivation to matrix normalization, graph embeddings, and spectral arguments. Readers outside these areas may struggle to distinguish the representation-learning objective, the computational task being proved hard, and its implications for learning.

Questions for authors
  1. Does the hardness result extend to formulations that replace exact centering and whitening with soft penalties or approximate constraints?

  2. What do the results imply for learning practically useful representations at moderate approximation accuracy, particularly with a small number of actions? Could you provide evidence connecting optimization error in the proposed objective to downstream prediction or control performance?

6 comments
AuthorsOpenReview ↗

Author Repsonse

We would like to thank the reviewer for their careful and detailed review of our work. Below we hope to address some of your concerns.

Q1/W2. Does the hardness result extend to formulations that replace exact centering and whitening with soft penalties or approximate constraints?

Yes, and we agree that connecting our results more closely to practical predictive representation learning would strengthen the paper. We have extended Theorem 2 to a specified soft penalty with fixed coefficients and to approximate normalization at explicit tolerances. Both extensions retain inverse polynomial approximation hardness for scalar population prediction. These results are provided in Appendix D.1. This is our proof sketch.

Proof sketch. We work in the scalar population setting of Theorem 2, with equally weighted actions and linear predictors without intercepts. Write h=n xh=\sqrt n\,x, u=1/nu=\mathbf1/\sqrt n, q=∥x∥2=E[h2]q=\|x\|^2=\mathbb E[h^2], and c=u⊤x=E[h]c=u^\top x=\mathbb E[h]. Let F(x)=m−1∑a(x⊤Tax)2F(x)=m^{-1}\sum_a(x^\top T_ax)^2 and retain JJ for its maximum over centered unit features. Minimizing over the linear predictors as in Section 2 gives L(x)=q−F(x)q(q>0),L(0)=0.L(x)=q-\frac{F(x)}q\quad(q>0),\quad L(0)=0.

Soft penalties. Consider V=min⁡x{L(x)+2c2+(q−1)2}V=\min_x\{L(x)+2c^2+(q-1)^2\}, with fixed penalty coefficients. For a nonconstant feature, decompose x=cu+q−c2 yx=cu+\sqrt{q-c^2}\,y, where yy is centered and has unit norm. Convexity of the square gives L(x)≥(q−c2)(1−F(y))L(x)\ge(q-c^2)(1-F(y)). Using F(y)≤JF(y)\le J yields

L(x)+2c2+(q−1)2≥q(1−J)+(q−1)2+(1+J)c2L(x)+2c^2+(q-1)^2\ge q(1-J)+(q-1)^2+(1+J)c^2.

This bound also holds for constant features. The quadratic in qq is minimized at q∗=(1+J)/2q_*=(1+J)/2. Taking x=q∗ y∗x=\sqrt{q_*}\,y_*, where y∗y_* is an original optimizer, attains the lower bound. Therefore,

V=g(J):=34−J2−J24.V=g(J):=\frac34-\frac J2-\frac{J^2}{4}.

The attaining feature is centered and nonzero, and its second moment q∗q_* can differ from one.

Approximate normalization. Suppose ∣c∣≤δc|c|\le\delta_c and ∣q−1∣≤δw|q-1|\le\delta_w, where δc,δw≥0\delta_c,\delta_w\ge0 and δw+δc2<1\delta_w+\delta_c^2<1. Centering and normalizing gives y=(x−cu)/q−c2y=(x-cu)/\sqrt{q-c^2}, whose denominator is positive. Substituting the same decomposition into LL, and using ∥Ta∥2≤1\|T_a\|_2\le1, gives

∣L(x)−(1−F(y))∣≤∣q−1∣+4c2≤Eδ:=δw+4δc2|L(x)-(1-F(y))|\le |q-1|+4c^2\le E_\delta:=\delta_w+4\delta_c^2.

The uniform bound and inclusion of the exact normalized domain imply that the relaxed minimum loss ℓδ\ell_\delta satisfies

1−J−Eδ≤ℓδ≤1−J1-J-E_\delta\le\ell_\delta\le1-J.

To transfer hardness, reuse the inverse polynomial gap Δ\Delta from Theorem 2. Since −g′(v)=(1+v)/2≥1/2-g'(v)=(1+v)/2\ge1/2 on [0,1][0,1], the soft objective retains a gap of at least Δ/2\Delta/2. Approximate normalization retains a gap of at least Δ−Eδ\Delta-E_\delta. The original threshold comparison therefore establishes hardness at additive accuracy ε\varepsilon whenever 2ε<Δ/22\varepsilon<\Delta/2, Eδ+2ε<ΔE_\delta+2\varepsilon<\Delta. These conditions can be met with inverse polynomial tolerances and accuracy. Appendix D.1 gives the complete proof and explicit parameter choices.

The construction in Theorem 2 therefore yields hard instances for both formulations whose kernels are strictly positive, with spectral gap 3/43/4 and centered operator norm 1/41/4. The added penalties and moment constraints have rational coefficients in hh, and the new tolerances and thresholds have O(log⁡N)O(\log N)-bit descriptions, so both reductions run in polynomial time.

AuthorsOpenReview ↗

Author Repsonse Part 2

Q2/W1. What do the results imply for learning practically useful representations at moderate approximation accuracy, particularly with a small number of actions?

This is a good question. Our original approximation algorithm gives polynomial time guarantees for a fixed number of independent action operators, which limited the practical relevance of our results. Building on Theorem 6, we have extended our analysis to establish randomized polynomial time approximation of the scalar optimal value at any fixed additive accuracy and confidence, even when the number of independent action operators grows (Appendix B.6). Here is the proof sketch.

Fixed additive accuracy. For explicitly given rational symmetric stochastic kernels, the algorithm in Appendix J returns an estimate J^\widehat J of the scalar optimal value with additive error at most ε\varepsilon and probability at least 1−δ1-\delta. For 0<ε≤10<\varepsilon\le1 and 0<δ<10<\delta<1, its bit complexity is

\operatorname{poly}(n,m,L,b),$$ where $L$ is the input encoding length and $b$ encodes $(\varepsilon,\delta)$. For fixed accuracy and confidence, this is polynomial in the input size even when the number of actions grows. ***Proof sketch.*** The key step is to approximate the objective uniformly over all centered unit encoders using a small sample of actions. Let $B_a=T_a-\mathbf1\mathbf1^\top/n$ and $f(x)=\frac1m\sum_a(x^\top B_ax)^2$, $J=\max_{x\perp\mathbf1,\|x\|=1}f(x)$. Sample $k$ actions $A_1,\ldots,A_k$ independently and uniformly with replacement from the known action list, and form $f_k(x)=\frac1k\sum_{j=1}^k(x^\top B_{A_j}x)^2$. To obtain simultaneous control over all encoders, use the identity $(x^\top B_ax)^2=(x\otimes x)^\top(B_a\otimes B_a)(x\otimes x)$. Each $B_a\otimes B_a$ is symmetric with operator norm at most one. Matrix Bernstein concentration therefore controls the difference between the sampled and full averages of these matrices. Since $\|x\otimes x\|=1$ for every feasible encoder, a sample of size $k=O\!\left(\varepsilon^{-2}\log(n/\delta)\right)$ suffices to give, with probability at least $1-\delta/2$, $\sup_{x\perp\mathbf1,\|x\|=1}|f_k(x)-f(x)|\le\frac{\varepsilon}{2}$. Taking maxima gives $|J_k-J|\le\varepsilon/2$, where $J_k$ is the sampled optimum. The sampled family has effective action rank at most $k$. Using the spectral formulation of **Theorem 6**, we approximate $J_k$ within $\varepsilon/2$ by a constructive grid over action coefficients with $(1+1/\varepsilon)^{O(k)}$ points. Each point requires computing a largest eigenvalue. Combining the two approximation errors gives $|\widehat J-J|\le\varepsilon$. For fixed $\varepsilon$ and $\delta$, we have $k=O(\log n)$, so the grid has polynomially many points. Appendix B.6 gives the complete implementation and bit complexity analysis.
AuthorsOpenReview ↗

Author Repsonse Part 3

Q2/W3. Could you provide evidence connecting optimization error in the proposed objective to downstream prediction or control performance?

Reducing the optimization error of our objective can benefit downstream prediction. We explain this connection theoretically and provide empirical evidence from experiments on fixed external prediction targets.

Theory. Khetarpal et al. [1, Theorems 4 and 5] connect self-prediction conditioned on actions to a shared low-rank approximation of the dynamics. Under their assumptions, they also give an interpretation through modified one-step value prediction averaged over isotropic random rewards. Building on this interpretation, we can make the role of optimization accuracy explicit in our scalar setting.

Consider our symmetric kernels with uniform stationarity and a centered unit encoder xx, corresponding to the feature h=n xh=\sqrt n\,x. Write δ(x)=J−F(x)\delta(x)=J-F(x) for its latent optimization gap. Let Ba=Ta−11⊤/nB_a=T_a-\mathbf1\mathbf1^\top/n and Px=xx⊤P_x=xx^\top. The squared error of the shared dynamics approximation satisfies

\quad D(x)-D^*=\delta(x),$$ where $D^*$ is the minimum over centered unit encoders. The equality follows by expanding the squared norm. For any fixed target $g$ with mean zero and variance one, let $R_g(x)$ denote the risk of its optimal population linear predictors from $h(S)$. Let $R_g^{\mathrm{Bayes}}$ denote the minimum prediction risk using the full state and action. Predicting $g(S')$ through $x$ gives $$R_g(x)-R_g^{\mathrm{Bayes}} =\frac1{mn}\sum_a\|(I-P_x)B_ag\|_2^2 \le D(x) =D^*+\delta(x).$$ Here the inequality uses $\|g\|_2^2=n$ and $(I-P_x)B_a=(I-P_x)(B_a-P_xB_aP_x)$. Reducing the latent gap therefore tightens a prediction error bound whose other term is the best achievable error of the shared dynamics approximation. **Experiments.** To examine whether optimizing this objective yields prediction gains, we evaluated learned encoders on four fixed targets across $240$ synthetic Markov kernel families. These targets comprise three next-state coordinates and an independent random state function. With optimal population linear heads, both Riemannian ascent and SLSQP reduced mean MSE on all four tasks relative to matched random initial encoders. The absolute reductions were $0.0101$ to $0.0117$ on the coordinate tasks and approximately $0.0039$ on the random target. We further examined how optimization gaps relate to prediction errors among the ten trained encoders within each kernel family. For Riemannian ascent, the mean Spearman correlations between the gap and external excess risk were positive on all four tasks, ranging from $0.29$ to $0.51$. These averages use the $212$ of $240$ families with defined correlations, and SLSQP gave similar results. This supports an association between smaller optimization gaps and better downstream prediction. Individual comparisons also show how this relationship depends on the prediction target. For Riemannian ascent, we compared the first start's final encoder with the best of ten final encoders selected by the latent objective. The objective improved in $85$ families, with higher prediction MSE on the first coordinate in $37$ of them. Such reversals are possible because changing the encoder also changes its latent prediction target, while the external target remains fixed. The two objectives can therefore favor different encoders. [1] Khetarpal, K., et al. A Unifying Framework for Action-Conditional Self-Predictive Reinforcement Learning. AISTATS, 2025. > W4. Readers outside these areas may struggle to distinguish the representation-learning objective, the computational task being proved hard, and its implications for learning. We understand the reviewer's concern that the text may be difficult for readers outside the field to follow. We have revised Section 2 to clarify how the predictive learning objective leads to the computational problem studied in our theorems.

Comments on the paper

2 comments
AuthorsOpenReview ↗

General Comment

We would like to thank all the reviewers for their time and attention to our work. Their comments have helped us to improve and sharpen the paper. In general, the reviewers praised the research question and motivation (L2Lx, bsNt), the hardness result for rapidly mixing kernels (Huje, L2Lx, bsNt), and the complementary structural tractability results (Huje, L2Lx, bsNt). In addition, the reviewers shared concerns that we have tried to address. To highlight the largest changes, we have:

  1. Extended our theory to cover more forms of predictive representation learning.
  2. Added experiments that directly train encoders and evaluate external prediction performance.
  3. Extended our complexity analysis to show that the scalar optimal value can be efficiently approximated at fixed accuracy.

Broader Formulations. First, some reviewers raised concerns about whether our theory applies to more forms of predictive representation learning. Specifically, they asked (i) whether the results extend to approximate normalization or soft penalties (L2Lx), and (ii) whether the sampled guarantees apply to fitted empirical prediction loss (bsNt). We have added results addressing both points. (i) For scalar representations with linear predictors without intercepts, we show that replacing exact normalization with a specified penalty on the feature mean and second moment preserves the population hardness result. The penalty coefficients are fixed constants. We also bound the change in prediction loss caused by approximate normalization (our response to Reviewer L2Lx, Q1/W2). (ii) Separately, for independent stationary transition pairs, we give conditions on each action's empirical state marginals under which guarantees for the sampled objective transfer to fitted empirical prediction loss. This comparison holds uniformly over normalized encoders, allowing the same samples to be used for normalization, encoder selection, and predictor fitting (our response to Reviewer bsNt, Q2).

Experiments. Some reviewers were concerned that the original experiments mainly illustrated the theoretical constructions. Specifically, they questioned (i) the use of simplex optimization and operators that were not stochastic (bsNt), and the relevance of dense constructions to sparse environments (Huje). Another concern was (ii) whether improving the latent prediction objective helps with external prediction or control (L2Lx). (i) We have added experiments that directly optimize the full scalar encoder on valid Markov kernels. These include a controlled study of action structure (our response to Reviewer bsNt, Q1/W1) and a separate study of sparse transitions (our response to Reviewer Huje, W3). Both Riemannian ascent and SLSQP succeeded on all 240 kernel families in each study, achieving certified optimality gaps of at most 6.25×10−56.25\times10^{-5} with ten starts in the controlled study and 10−210^{-2} with one start in the sparse study. (ii) We also evaluate the encoders from the controlled study on fixed external targets at the next state (our response to Reviewer L2Lx, Q2/W3). Relative to matched random initial encoders, both optimizers reduced mean prediction MSE across the 240 kernel families on all four fixed external targets. The absolute reductions were 0.01010.0101 to 0.01170.0117 for the three coordinate targets and approximately 0.00390.0039 for the random target.

Approximation accuracy. Finally, some reviewers asked what the hardness result implies at moderate accuracy and with few actions (L2Lx), and how it relates to the apparent ease of optimization in our experiments (Huje). Our original lower bound concerns inverse polynomial accuracy. We have extended our complexity analysis to show that, in the scalar setting, the optimal value can be approximated in randomized polynomial time at any fixed additive accuracy and confidence. This result allows the number of actions to grow with the input size. For a fixed number of actions, the original Theorem 6 already gives polynomial time approximation of the scalar optimal value even at inverse polynomial accuracy (our response to Reviewer L2Lx, Q2/W1). Thus, the successful optimization observed in our experiments is compatible with the original worst case lower bound.

Overall, we would like to thank the reviewers for their time and effort, and look forward to hearing what they have to say in response.

AuthorsOpenReview ↗

PDF Change

We thank all three reviewers again for their comments. We have uploaded the revised PDF. To briefly explain our submission edit, we clarified how the predictive learning objective leads to our computational problem (Section 2), extended the theory to relaxed normalization, fitted empirical prediction loss, and sparse transitions (Appendices B and D), and added experiments on direct encoder training and external prediction (Section 6 and Appendix F).

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.