- 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 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
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 and be the empirical source and target state distributions for action , and let be the pooled source distribution. We use scalar features centered and normalized under , with linear prediction heads without intercepts. Suppose 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.Reminder
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.
Author Repsonse
We thank the reviewer for their attention and reading of our paper. Below we try to address the concerns you raised.
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} and its average operator norm residual over η/β∈{0,0.05,0.15,0.30}, with β=1/4. The centered operator norms remain close to β, and the absolute spectral gaps are at least 3/4. For positive residuals, the full action span is six, while the prescribed approximation has span r. 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−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.
Averaged across the four residual levels, the r=1 group had the highest success rate per run for both methods. For r=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/240 and 159/240 families from the first start, respectively, while selecting the best of ten starts increased both to 240/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 16 or 64 states. The results are given in our response to Reviewer Huje, W3(ii).
We understand the reviewer's concern about the size of this sufficient bound. Actually, the N9 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.