acceptodds
Under review as a conference paper at ICLR 2027

Choosing What to Remember: Robust Offline Reinforcement Learning with History Representations

16 views

Abstract

Robust offline reinforcement learning uses recorded data alone to learn policies that perform reliably under uncertainty. With delays or partial observations, policies often use history representations that map observed histories to represented states. The joint distribution of reward and next represented state can then depend on the policy, even at a fixed represented state and action in an unchanged environment. We develop a framework for conditional operator robustness under history representations and propose Conditional Operator Robust Fitted Q-Iteration (COR-FQI). Its robust Bellman recursion chooses actions that maximize the worst-case expected sum of immediate reward and continuation value over uncertainty sets. These sets are constructed to account for differences in conditional Bellman expectations among histories sharing a represented state, in addition to finite-sample estimation error and specified environmental changes. Under stated assumptions, we establish lower confidence bounds on the learned policies' worst-case expected returns without requiring the represented process to be Markov. The guarantees cover tabular settings and function approximation, with additional coverage conditions and uniform error bounds for the latter. These bounds hold simultaneously across a finite family of representations and provide a performance guarantee for choosing the representation–policy pair with the largest lower confidence bound. Tabular experiments show informative bounds and selection of longer memory with more data, while implementations based on function approximation show empirical robustness to perturbations, delays, and distribution shift.

Primary area:
reinforcement learning
Keywords:
Robust Reinforcement Learning, Non-Markovian Dynamics, Fitted Q-Iteration

Reviews

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

The paper studies robust offline reinforcement learning when an agent uses a compressed version of its history. Its key observation is that changing the policy can change which histories occur within the same represented state, making predictions learned from logged data unreliable. COR-FQI accounts for this additional uncertainty and selects a history representation using a conservative performance estimate. The paper provides theoretical guarantees, tabular experiments on FrozenLake, and empirical evaluations with neural networks.

Critical strengths

This paper addresses a practical challenge in partially observable offline RL: retaining too little history can hide information needed for good decisions, while retaining too much makes learning harder with limited data. This trade-off is particularly relevant to robotics, autonomous systems, and industrial control, where observations or actions may be delayed and collecting new interaction data can be costly or risky. Selecting memory using conservative performance estimates could be a promising direction to learn policy that is more reliable during deployment.

Critical weaknesses
  1. The writing and rigor of this paper are poor. A lot of definitions are introduced with words rather than formal mathematical formulas. For example, in row 131, the definition of Lm\mathcal{L}_m is stated by words: a conditional distribution under MM, which is fully unspecified. This writing ambiguity makes the paper hard to read.

  2. The proposed method needs reliable bounds on how much outcomes can differ between histories assigned to the same represented state, including histories absent from the dataset. Finer logging information helps, but still requires additional assumptions and coverage. The FrozenLake example uses a known delay structure, leaving applicability to less structured environments unclear.

Questions for authors
  1. How can useful history-variation bounds be obtained when neither a known delay model nor a predictively sufficient finer representation is available?

  2. Compared with prior literature, what is the advancement in theory and algorithm of this paper?

3 comments
AuthorsOpenReview ↗

(Part 1/2) Response to Reviewer 2gMY

We thank the reviewer for their careful reading. The revision keeps the original statements of the main results and their numbering, and adds material around them; all changes are marked in red in the revised paper.

W1. Writing and rigor: definitions are given in words (for example, the logging distribution).

We have replaced the verbal definitions by formal ones. The logging weights are now defined in Section 3.1 as a regular conditional distribution of the history given the represented state and the action, under the distribution of a recorded trajectory. The dataset, the visit counts and the empirical distributions are defined by formulas in Section 4.1, the data condition of Assumption 1 is stated formally, and the visit averages in Proposition 4 are written out. The distribution of a recorded trajectory, the reset distribution and the behavior policy are introduced in Section 2.1. The proofs in the appendix are written in full sentences, and each begins with a proof sketch.

W2. The method needs bounds that also hold for histories absent from the dataset. Finer logging still needs assumptions and coverage. FrozenLake uses a known delay structure.

The first two statements are correct, and the paper now says so. Section 4.2 states that the bound must hold for all histories of a cell, including histories that are absent from the dataset, and that it is therefore a statement about the system and not an estimate; Proposition 1 shows that no method can obtain it from the compressed data. The same section states that calibration from finer logs still requires an exhaustive partition and valid residual bounds. A conservative bound remains safe, since it lowers the certificate without invalidating it.

On the third statement, we have made two additions. First, the sources of the bound are no longer restricted to delays: Lemma A.5 covers quantities that are recorded coarsely, and Lemma A.6 covers a hidden state that mixes, and neither uses a delay structure. Second, Appendix C.2 adds a tabular study without delay structure, a grid-robot navigation task in which two junctions look alike and a landmark seen earlier identifies the correct exit. In this study the certificates of the candidate representations cross as the data grow, and selection between two insufficient representations returns a policy that attains the full-history optimum. Without the bound, the certificates are invalid: under a history-dependent behavior policy, all 60 fits at the two largest sample sizes report a lower bound above the true return, 0.870 against 0.76 at N = 100,000.

The FrozenLake experiment also reports the effect of the inputs. Doubling the supplied bound lowers the certificate from 0.333 to 0.133, and calibration from logged labels, without the supplied bound, gives 0.343. Appendix C.1 now adds a sensitivity curve (Figure 4): the certificate of the one-command memory decreases smoothly as the assumed bound grows, from 0.403 at 0.075 to 0.333 at the supplied value 0.1 and to 0.218 at 0.15, so that a required return of 0.2 remains certified for any assumed bound up to 0.15.

AuthorsOpenReview ↗

(Part 2/2) Response to Reviewer 2gMY

Q1. How can useful bounds be obtained when neither a delay model nor a sufficient finer representation is available?

Section 4.2 and Appendix A.11 give four routes. Under smooth dependence (Lemma A.5), the designer states the resolution of a recorded quantity and the sensitivity of the outcome to it, and no delay is involved. Under fading memory (Lemma A.6), a hidden state that mixes gives a bound that decreases geometrically in the window length; this lemma requires bounded likelihood ratios, and the paper states this scope. With a finer label that is itself not sufficient (Proposition 4), only a residual bound is required, and the same proposition gives a lower bound that detects an insufficient representation from data. When no bound is known (Proposition A.7), the certificates for all assumed values hold on one event, and the designer can report the largest conditional variation under which a required return remains certified; the new sensitivity curve for FrozenLake in Appendix C.1 is an example.

The grid-robot study illustrates two of these routes. With the bound obtained from finer logs, the selected certificate reaches 0.709 at N = 100,000, against 0.826 with the supplied bound, for the same selected policy. The lower bound of Proposition 4 identifies both insufficient representations from data, with no false alarm at the cells where the representation is sufficient.

Q2. What is the advancement in theory and algorithm over prior literature?

The introduction now lists four contributions. The first is an impossibility result: the radius required after compression is characterized exactly, and the compressed data cannot identify it (Proposition 1). The second is calibration: the sets contain the outcome distribution of every pooled history, for all candidate representations simultaneously, although the data are dependent and not identically distributed (Theorem 3). The third is certification without a Markov state: the recursion on a represented state is a lower bound on the worst-case return, and an upper value bounds every history-dependent policy (Theorem 5). The fourth is certified selection: all certificates hold on one event, so that the representation with the largest certificate is selected from the same data without loss of confidence, with a computed upper bound on the loss relative to the best history-dependent policy (Theorem 6).

Thanks for the authors' response. However, given the revised version, I still find it hard to follow and understand the paper. I believe that the paper is not ready for acceptance at a top-tier AI conference. Therefore, I decide to maintain my score.

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

This paper studies robust offline RL with history-dependent dynamics, including delayed feedback and partial observations. Previous work has considered both Markov and non-Markov settings. This paper focuses on choosing among given history representations, even when they omit useful information.

For each candidate representation, the algorithm constructs uncertainty sets that contain the relevant true outcome distributions with high probability, under the stated assumptions. It then uses robust value iteration to obtain a policy and a lower bound on its worst-case return. Finally, it selects the representation and policy with the largest lower bound.

Critical strengths

The paper considers a challenging setting. Its uncertainty sets support performance guarantees that remain valid after selecting a representation from the candidate family.

Critical weaknesses

The theoretical guarantees rely heavily on Assumption 1, which is too strong in my opinion. The learner is given uniform bounds on the effects of (i) information lost through history representation and (ii) environmental changes. These bounds already supply substantial information needed to handle the challenging setting. Given these inputs, the algorithm follows naturally from existing robust dynamic programming methods. The paper needs to explain more clearly what its contribution adds beyond these methods.

The paper is difficult to follow and provides too little intuition for its definitions, assumptions, and theoretical results. It should explain why these objects are introduced and how they support the algorithm, using simple examples where possible. The preliminaries also lack adequate background on robust RL, particularly the role of uncertainty sets and the robust Bellman operator. This background would help distinguish established methods from the paper's contribution.

Several notation choices and experimental details are insufficiently explained when introduced. For example, ψ\psi is used for both the logging distribution and arbitrary reweighting distributions in Proposition 1 (p. 3). The subscript in ete_t indexes time, while the experimental eme_m indexes memory length; this distinction is clarified only in Appendix A.1 (p. 12). Understanding the command-age mechanism in the modified FrozenLake experiment and the derivation of its calibration inputs requires consulting Appendices B.7 and C.1 (pp. 22–23). These explanations should appear where the concepts are introduced. Expanding the short notation table in Appendix A.1 and placing it near the preliminaries would also help.

In Figure 1(a), UU remains close to one, the maximum possible return, and therefore provides an essentially trivial upper bound. Most of the interval tightening comes from the lower bound. This limits the experiment's evidence for the usefulness of the upper certificate.

Questions for authors

How large is B(e)B(e) in Theorem 5 (p. 6), and when does it meaningfully improve on the trivial return bound? Since B(e)B(e) accumulates horizon-weighted TV diameters, even diameters of order 1/T1/T can yield a bound of order TT. This suggests that informative guarantees require particularly small TV diameters. Please clarify the dependence of B(e)B(e) on sample size, horizon, and the supplied history-variation and deployment bounds.

Why is the method called Fitted Q-Iteration? Algorithm 1 (p. 6) performs exact tabular Bellman updates without an explicit fitting step, whereas fitting appears in the approximate neural implementation, Algorithm 2 (p. 24). Please clarify the relationship between the two procedures and the reason for this name in the main text.

3 comments
AuthorsOpenReview ↗

(Part 1/2) Response to Reviewer ETmq

We thank the reviewer for their careful reading. The revision keeps the original statements of the main results and their numbering, and adds material around them; all changes are marked in red in the revised paper.

W1a. Assumption 1 is too strong: uniform bounds on (i) information lost through the representation and (ii) environmental changes.

Each part of Assumption 1 has a counterpart in the literature, and neither part is stronger than its counterpart; the introduction and the remark after Assumption 1 now make this explicit. The bound on environmental change is the specification of the uncertainty set, which every robust method receives as an input. The bound on the information lost through the representation weakens the assumption of a Markov state on which existing certificates rest: a Markov state requires that histories with the same state do not differ at all, whereas we allow a difference up to the bound. A bound of the same kind defines approximate information states (Subramanian et al., 2022), where it is uniform over all histories.

The bound in our paper is not uniform. It is stated separately for each represented state and action, the value 1 is always valid, and an overestimate yields a smaller certificate, never an incorrect one. The bound cannot be dropped, because Proposition 1 shows that the compressed data do not identify it. Section 4.2 and Appendix A.11 show how the bound can be supplied without a model of the omitted information.

W1b. Given these inputs, the algorithm follows naturally from existing robust dynamic programming. What is the contribution?

The computation is indeed the robust backup of an existing method, with one additional term in the radius, and the introduction now says so. The contribution is the theory that makes this computation valid after history compression. The introduction lists four results. (C1) The additional term is necessary, and the compressed data cannot reveal its size (Proposition 1). (C2) The sets are calibrated from pooled outcomes that are neither independent nor identically distributed, for all candidate representations simultaneously (Theorem 3). (C3) Existing analyses assume a Markov state; on a represented state the recursion is no longer the Bellman equation satisfied by the value of the policy, and we prove, by a comparison at every history, that it remains a lower bound on the worst-case return (Theorem 5). (C4) The certificates of all candidates hold on one event, so that the representation with the largest certificate can be selected from the same data without loss of confidence, with a computed upper bound on the loss relative to the best history-dependent policy (Theorem 6).

A new paragraph in the introduction explains why adding this term to the radius of an existing method is not sufficient: the size of the term cannot be obtained from the data, existing guarantees assume a Markov state, and a uniform term would penalize the represented states without conditional variation, whereas the term in COR-FQI is specific to each represented state and action.

W2. Too little intuition; missing background on robust RL.

Section 2.2 now contains a background paragraph that introduces uncertainty sets and the robust Bellman recursion, and names the two properties on which the standard certificate rests: (P1) every state and action has one nominal distribution, and (P2) the state is Markov. The following sections show where each property fails after compression and which result replaces it. Proposition 1 and Theorem 3 replace (P1), and Theorem 5 replaces (P2). This structure separates the established method, which is described in Section 2.2, from our contribution in Sections 3 to 5.

W3. Notation and experimental details.

The logging weights are now denoted by ψ and are defined formally in Section 3.1, and an arbitrary reweighting is denoted by ω. The subscript of a representation denotes the stage; in the FrozenLake experiment, where the subscript denotes the memory length, Section 6.1 now says so explicitly. Section 6.1 also describes the command-age mechanism and states the meaning of the supplied bounds in the main text, with the derivation in Lemma B.7. The notation table has been expanded and is referenced at the start of Section 2; it remains in Appendix A.1 because the page limit did not allow us to move it into the main text.

W4. The upper value in Figure 1(a) is close to one and nearly trivial.

We agree. Section 6.1 now states that the upper value is not informative in this experiment and that the gap bound W = 0.315 does not establish near-optimality. An informative upper value requires radii below 1/(T+1), as the answer to the next question explains. The second tabular study shows the same conservatism and reports it: at N = 100,000 the selected policy is optimal, yet the computed gap bound is 0.174 (Appendix C.2).

AuthorsOpenReview ↗

(Part 2/2) Response to Reviewer ETmq

Q1. How large is B(e), and when does it improve on the trivial bound?

The remark after Theorem 5 and Appendix A.7 now answer this question. B(e) is at most min{T, T(T+1)ε}, where ε is the largest radius, and it is therefore below the trivial bound T only if ε < 1/(T+1); the comment is correct. The radius is the sum of an estimation term, which decreases with the number of visits roughly as the square root of log(n)/n, and the terms b and ρ, which do not decrease with the sample size. The bound B(e) holds for every bounded value function and is therefore pessimistic; the computed width U(e) − L(e) can be much smaller. In FrozenLake the bound exceeds 2.5, which is above the maximal return of 1, whereas the computed gap bound is 0.315.

Q2. Why “Fitted Q-Iteration”, when Algorithm 1 is tabular?

Algorithm 1 is fitted Q-iteration in which the regression is exact, because the tabular class contains every target. Algorithm 2 in Appendix C.3 keeps the same steps and fits the regression for continuous spaces. Section 4.3 now states this relationship in the main text. The name follows RFQI, with which the method coincides on a predictively sufficient representation (Proposition B.2).

I thank the authors for their detailed response. However, I am still not convinced by the paper's presentation. Moreover, the paper has been substantially revised during the discussion period, which suggests that a fresh review process would be more appropriate. In addition, I find the theoretical and empirical results insufficiently strong in my opinion. Therefore, I would like to maintain my current rating.

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

The paper explores offline RL when the policy acts on a representation mapping observation, action, reward histories to a state, however, these histories mapped to the same state can now have different conditional distributions from then onwards. The work tackles this by building TV balls around the pooled outcome distribution and calculates the radius as the sum of an estimation term, the supplied history-variation bound and a deployment radius, which allows them to define a lower certificate on the worst case return of the learned polucy and the upper bound on the full history optimum J∗J^*, and choosing the representation with the largest certificated givees a bound on the selected policy's gap to J∗J^*.

Critical strengths

The problem statement in the paper is well motivated, and tackles a real problem where when a policy compresses its history, the stored estimates become misleading. The proofs in the paper also do not assume that the compressed states are Markov, and the guarantees hold with data collected with a changing policy over random sample size. The relevant theory seems accurate, although I did not read the appendix thoroughly. They also show longer memory does not necessarily give you a better certificate, and their method reduces to RFQI in the Markovian scenario. The authors also provide relevant experimental results on multiple domains.

Critical weaknesses

w1: the bound on the outcome distribution of different histories bb needs to be supplied, which the paper suggests can be done either from prior knowledge or finer logged information, so it seems like a good bb value in practice can require nearly as much knowledge as sufficient representation, could you clarify if this is the case? If so, the practical usefulness seems quite limited.

w2: The idea of using bb is similar to that in Petrik et al.[1], and needs direct comparison. The literature review section needs more work.

w3: For function approximations, the assumptions are quite strong, when you cannot check the error bounds required from the data.

w4: The paper and the notations are quite dense, it is a bit difficult to read.

[1] Marek Petrik and Dharmashankar Subramanian. 2014. RAAM: the benefits of robustness in approximating aggregated MDPs in reinforcement learning. In Proceedings of the 28th International Conference on Neural Information Processing Systems - Volume 2 (NIPS'14), Vol. 2. MIT Press, Cambridge, MA, USA, 1979–1987.

Questions for authors

q1: See w1 and w2.

q2: Can you clarify which family E is used for each of the domains in the experiments in Section 6.2?

2 comments
AuthorsOpenReview ↗

(Part 1/2) Response to Reviewer Yy1e

We thank the reviewer for their careful reading. The revision keeps the original statements of the main results and their numbering, and adds material around them; all changes are marked in red in the revised paper.

w1: the bound on the outcome distribution of different histories needs to be supplied, which the paper suggests can be done either from prior knowledge or finer logged information, so it seems like a good value in practice can require nearly as much knowledge as sufficient representation, could you clarify if this is the case? If so, the practical usefulness seems quite limited.

It does not require. We now address this question directly in Section 4.2 . A valid bound requires only knowledge of how often, or how strongly, the omitted information matters; it requires neither the identity of that information nor its dynamics. Appendix A.11 states three such conditions, proves them, and illustrates each with a short design example. If the outcome depends on the omitted history only with probability q, then q is a valid bound (Lemma A.4). If the outcome depends smoothly on a quantity that is recorded coarsely, the bound is the sensitivity multiplied by the resolution (Lemma A.5). If a hidden state mixes, the bound for a window of m transitions decreases geometrically in m (Lemma A.6). In addition, Proposition 4 obtains the bound from finer logged information, and Proposition A.7 shows that, when no bound is known, the certificates for all assumed values of the bound hold on one event with no confidence loss.

Two further points reduce the burden on the designer. First, the value 1 is always valid, and an overestimate of the bound yields a smaller certificate, never an incorrect one. Second, a known sufficient representation is not necessarily the representation to use, because it has the fewest visits per represented state. In FrozenLake at N = 1,000, always choosing the sufficient memory loses 0.606 of the worst-case return, whereas selection by certificate loses 0.0004 (Section 6.1). Proposition 1 shows that the bound cannot be avoided altogether, since the compressed data do not identify it.

w2: The idea of using is similar to that in Petrik et al.[1], and needs direct comparison. The literature review section needs more work.

We have added the comparison to the related-work paragraph of the introduction and to Appendix E. RAAM aggregates the states of a known Markov model for planning, and an adversary chooses the weights within an aggregate state. Proposition 1(i) concerns the corresponding reweighting of histories within a cell, so the mechanism is shared, and the paper now says so. The present paper adds three elements that RAAM does not address: the required radius cannot be identified from the compressed data, the sets are calibrated from a finite dataset of a process that is not Markov, and the aggregation itself is selected by certificates. Appendix E now also states the contrast with Huang et al. (2025), with approximate information states (Subramanian et al., 2022), and with Hutter (2014).

w3: For function approximations, the assumptions are quite strong, when you cannot check the error bounds required from the data.

We agree, and the revised paper states this limitation explicitly; the verification of these error bounds from data is left for future work, as the conclusion says (Section 7). The results for approximate backups (Theorem A.3 and Theorem B.3) hold under conditions that a training loss or a held-out error does not establish; the paragraph “Further results” in Section 5.2 says this, and Appendix D.1 repeats that the returns reported in Section 6.2 are empirical and are not certificates. The certified claims of the paper are the tabular results, Theorems 3, 5 and 6, and they are tested in the two tabular studies (Section 6.1 and Appendix C.2).

w4: The paper and the notations are quite dense, it is a bit difficult to read.

Sections 2 to 5 have been revised so that each object is introduced by the reason for which it is needed. Section 2.2 names the two properties, (P1) and (P2), on which the standard robust certificate rests. Section 3 shows why (P1) fails after compression. Section 4 presents the construction in four steps and names the three obstacles, (O1)–(O3), that the calibration must overcome. Section 5 explains why (P2) fails and how Theorems 5 and 6 nevertheless provide the guarantee. Each main result is followed by a short remark on its proof, every proof in the appendix begins with a proof sketch, and the notation table in Appendix A.1 has been expanded.

AuthorsOpenReview ↗

(Part 2/2) Response to Reviewer Yy1e

Q2. Which family of representations is used in each domain of the function-approximation experiments?

Each benchmark uses one fixed representation, and no selection by certificates is performed in these benchmarks; selection is demonstrated in the two tabular studies. Appendix D.1 now states the representations. Hopper and HalfCheetah are evaluated at zero delay with the current observation. Inverted Pendulum is evaluated under an action delay of six steps, and the represented state consists of the current observation and the six actions that have been issued but not yet applied. MiniGrid Memory and Umaze-diverse use the feature vector of a RATE encoder that is trained first and then frozen; for Umaze-diverse the delay fraction is appended.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.