Approximate information state for approximate planning and reinforcement learning in partially observed systems

1. Introduction

• Reinforcement-learning theory has focused primarily on systems with full state observations, although many applications provide only partial observations.Source: §1 · p. 2
• Belief-state planning for partially observed systems requires a known model, limiting its use when reinforcement-learning agents operate in unknown environments.Memoryless and finite-memory policy approaches are described, but the paper notes that approximation guarantees are unavailable for such methods.Source: §1 · p. 2
• The paper formalizes information states for partially observed systems and gives equivalent methods for identifying them.Source: §1 · p. 3
• Approximate information states support approximately optimal policies, with performance loss bounded in terms of one-step approximation errors.The framework also covers observation and action compression, multi-agent systems, and approximation methods from prior work.Source: §1 · p. 3
• The framework extends approximate planning to decentralized partially observed systems using a common-information-based approximate information state.Source: §1 · p. 3
• The paper presents online policy-gradient algorithms that learn an approximate information state using multi-timescale stochastic gradient descent.Experiments span low-, moderate-, and high-dimensional partially observed environments.Source: §1 · p. 3

2.1 General model for a partially observed system

• The model treats each time step as taking an action and disturbance as inputs and producing an observation and reward, with policies choosing actions from past observations and actions.The exposition assumes finite action, disturbance, and observation sets, while noting that the analysis extends to general spaces under technical conditions.Source: §2.1 · p. 4

2.2 A dynamic programming decomposition

• Using the entire history as the state gives a recursive dynamic program for evaluating policies and finding an optimum, but it may be inefficient and serves as a reference for more efficient decompositions.The finite-horizon setup assumes known dynamics, reward functions, and disturbance law; with finite-valued variables, an optimal policy exists.Source: §2.2 · pp. 5–6, §2.1 · p. 5, §2.3 · p. 6

2.3 Information state and simplified dynamic programs

• An information state preserves expected rewards and predicts its own next value given the current history and action; useful compression also requires suitably small information-state spaces.An equivalent sufficient condition is recursive updating from the current information state, observation, and action, together with sufficiency for predicting the next observation; these conditions imply prediction of the next information state but are stronger than that property alone.Source: §2.3 · pp. 6–7
• An information state supports a dynamic program over compressed histories, whose maximizing actions yield an optimal policy when applied to the corresponding information states.The resulting value and action-value functions are defined on the information-state spaces rather than the full history spaces.Source: §2.3 · pp. 7–8

2.4 Examples of information state

• A non-trivial information state may not exist for a general model; its existence depends on the observation and reward functions and the primitive-noise law.The history itself is always a trivial information state, while the paper points to specific models whose information-state results are special cases of its later theorem.Source: §2.4 · p. 9
• Examples include the current state in an MDP, the absolute-value state in even MDPs, and the first state component when rewards ignore the second component.The cited even-MDP construction is from Chakravorty and Mahajan (2018); the irrelevant-component case is discussed in Feinberg (2005).Source: §2.4 · p. 9
• Theorem 5 recovers standard belief-state POMDP, Kalman-estimate LQG, and delayed-observation POMDP dynamic programs as special cases (Astr¨om, 1965; Smallwood and Sondik, 1973; Astr¨om, 1970; Bander and White, 1999).The respective information states are the posterior belief, conditional state estimate, and delayed-state belief together with the last δ control actions.Source: §2.4 · p. 10
• For machine maintenance, the inspection-time state and elapsed time, (Sτ, t −τ), form an information state (Eckles, 1968).The model’s objective is to minimize production, inspection, repair, and replacement costs.Source: §2.4 · p. 10

2.5 Discussion and related work

• The authors report no prior formal result defining information states and showing that they always imply a dynamic-programming decomposition.They note that earlier literature used the notion, but did not formally establish this general implication.Source: §2.5 · p. 11
• Unlike traditional state sufficiency for input-output mapping, an information state is sufficient for performance evaluation and thus dynamic programming.The paper also relates the notion to sufficient statistics for optimal control.Source: §2.5 · p. 11
• Information states are a one-step, Markovianized counterpart to belief-trajectory equivalence and PSRs, which concern future observations and may omit rewards; unlike PSRs and bisimulation equivalences, they cover finite and infinite horizons.The passage also relates belief-trajectory equivalence to predictive state representations and observable operator models.Source: §2.5 · pp. 11–12

3. Approximate planning in partially observed systems

• For machine maintenance, the countable information state (Sτ, t −τ) gives a simpler dynamic program than the belief-state approach and can be truncated to a finite-state approximation.Because this information state does not depend on machine transition probabilities or inspection and repair costs, it can also support reinforcement learning when those parameters are unknown.Source: §3 · p. 12

3.1 Integral probability metrics (IPM)

• Integral probability metrics compare distributions through a chosen function class, support weak-convergence analysis and sample estimation, and include bounded-Lipschitz and maximum mean discrepancy metrics.The paper uses maximum mean discrepancy in its later PORL algorithms because its optimizing function can be identified in closed form.Source: §3.1 · pp. 12–13, Examples of integral probability… · p. 13

3.2 Approximate information state (AIS) and approximate dynamic programming

• An approximate information state yields an approximate dynamic program, with bounds on value and action-value approximation and an approximately optimal policy.The approximation is defined through approximate satisfaction of the information-state properties.Source: §3.2 · p. 16

3.3 Examples of approximate information states

• The framework treats MDP model approximation and state abstraction as examples of approximate information states, and derives policy-approximation bounds for these settings.The paper also notes that its infinite-horizon generalization yields a policy approximation bound for state abstraction.Source: §3.3 · p. 19
• AIS bounds improve policy-approximation error by a factor of 1/(1 −γ) over Abel et al. (2016) and Francois-Lavet et al. (2019).For ε-sufficient statistics, the analysis gives an (ε span(r), 3ε)-AIS; Saldi et al. (2018) showed convergence under technical conditions but gave no error bound for a fixed quantization level.Source: §3.3 · pp. 20–21

3.4 Approximate policy evaluation

• Theorem 9’s bounds can be adapted to compare an arbitrary policy’s performance in an approximate model with its performance in the real model.The section introduces approximate policy action-value functions for this evaluation setting.Source: §3.4 · p. 21

3.5 Stochastic AIS

• Stochastic history compression supports learning discrete-valued AIS mappings by stochastic gradient descent, and the section establishes value-approximation and approximately optimal policy results for stochastic AIS.A stochastic mapping can also be represented as a deterministic mapping into distributions over approximate states.Source: §3.5 · pp. 22–23

3.6 AIS with action compression

• Action-quantized AIS provides value and policy approximation guarantees, while in MDPs the policy bound has no extra factor of 2 because quantized actions are executable in the original model.The MDP result assumes the quantized action set is a subset of the original action set.Source: §3.6 · pp. 24, 26

3.7 AIS with observation compression

• Observation compression is formulated as a new input-output system with compressed observations and rewards; a similar construction by Ha and Schmidhuber (2018) performed well empirically but lacked approximation guarantees.The framework generalizes AIS to accommodate compressed observations.Source: §3.7 · pp. 26–27, Figure 3 · p. 27
• For t=1 observation-compression AIS, the bounds of Theorem 9 hold.Source: §3.7 · p. 27

3.8 Discussion and related work

• AIS generalizes state discretization and aggregation; in some cases, Theorem 9 or 27 provides tighter bounds than prior results.Examples in Section 3.3 include results on state aggregation and latent state embedding in MDPs.Source: §3.8 · p. 27

Appendices.

• Bisimulation-metric methods aggregate states, whereas AIS need not; approximate PSR methods rely on PSR structure and are conceptually different from AIS.Bisimulation metrics yield Lipschitz value functions (Ferns et al. (2004, 2011); Castro et al. (2009)); PSR approximations include spectral learning and stochastic gradient descent, with error bounds (Rosencrantz et al. (2004); Boots et al. (2011); Hamilton et al. (2014); Kulesza et al. (2015b,a); Jiang et al. (2016); Wolfe et al. (2008)).Source: Appendices · pp. 27–28

4.2 A dynamic programming decomposition

• Because a general history-dependent policy lacks a recursive performance dynamic program in this setting, the section instead constructs recursively computable, arbitrarily precise bounds under the bounded-reward assumption.The authors note that general partially observed models lack a general method for identifying a time-homogeneous information state.Source: §4.2 · p. 29

4.1 System model and problem formulation

• Under uniformly bounded rewards, recursive upper and lower bounds can approximate the performance of any history-dependent policy arbitrarily precisely.The setup maximizes expected discounted total reward with discount factor γ ∈ (0, 1).Source: §4.1 · p. 28, §4.2 · p. 29

4.3 Time-homogeneous information state and simplified dynamic program

• A time-homogeneous information state yields a Bellman fixed point whose maximizing policy is optimal, but such a state may not exist for every partially observed model.The paper leaves conditions for existence of time-homogeneous information states open.Source: §4.3 · pp. 31–32

4.4 Time-homogeneous AIS and approximate dynamic programming

• For a time-homogeneous AIS, the approximate dynamic program bounds value- and action-value-function errors by α and supports an approximately optimal policy.The results also extend to approximate policy evaluation, stochastic AIS, action compression, and observation compression.Source: §4.4 · pp. 33–34

5.2 Common information based planning for Dec-POMDPs

• Under partial history sharing, a virtual coordinator observes common information and chooses prescriptions for agents; its policy has the same performance as the corresponding decentralized policy.Prescriptions encode the agents’ local-information-to-action rules.Source: §5 · p. 35, §5.2 · p. 37

5.1 Model of a Dec-POMDP

• The Dec-POMDP objective is to maximize team performance using policies that depend on agents’ available information.Each agent’s information may grow over time.Source: §5.1 · pp. 35–36

5.3 Common-information based AIS and approximate dynamic programming

• For the virtual coordinated system, a common-information AIS yields an approximate dynamic program with value-function errors bounded by α_t.The approach extends to approximate policy evaluation, infinite horizons, stochastic AIS, action compression, and observation compression.Source: §5.3 · pp. 38–39

6.1 The choice of an IPM

• The method uses KL-based upper-bound surrogates for total-variation or Wasserstein distances, or sample-computable RKHS-based MMD that avoids solving a linear program at every gradient step.For total variation, the proposed cross-entropy surrogate follows from Pinsker’s inequality.Source: §6.1 · pp. 40–41
• For continuous targets, the p = 2 MMD surrogate depends only on the predicted mean, so it is appropriate when the true distribution is expected to be near deterministic.For more stochastic observations, the authors suggest considering distance-based MMD with a different p, such as p = 1.Source: §6.1 · pp. 42–43

6.2 Learning an AIS for a fixed policy

• For a fixed policy, stochastic gradient descent learns AIS-generator parameters by combining reward-prediction and AIS or observation-prediction losses.The combined loss weights the squared losses using hyperparameter λ; the prediction distance can use a KL-based or distance-based MMD surrogate.Source: §6.2 · p. 43

6.3 AIS-based PORL

• Joint actor-only learning updates the AIS generator faster than the policy, while actor-critic learning adds a critic on a slower timescale; under standard technical conditions, the iterations converge to a stationary point of their ODE limits.At convergence, the paper states that approximation guarantees depend on ε and δ, which measure AIS approximation quality.Source: §6.3 · pp. 44–46

7. Experiments

• Across three environment classes, the experiments use an LSTM history compressor and feed-forward reward, observation-prediction, and policy networks, with a shared architecture within each difficulty class.The baseline uses LSTM actor and critic networks with PPO; high-dimensional environments are compared only with this baseline because planning is intractable.Source: §7 · pp. 46–47

7.1 Low-dimensional environments

• In Tiger, Voicemail, and CheeseMaze, AIS-based PORL and LSTM+PPO both converge close to the planning solutions relatively quickly.The low-dimensional comparison is shown for ten random seeds.Source: Figure 5 · p. 48, §7.1 · p. 49

7.2 Moderate-dimensional environments

• In RockSample and DroneSurveillance, both AIS-based algorithms converge close to the best planning solution; LSTM+PPO gets stuck in a local minimum in RockSample.For CheeseMaze, all learning algorithms outperform the best planning solution reported in the experiments.Source: §7.2 · pp. 49–50, Figure 6 · p. 49

7.3 High-dimensional environments

• For MiniGrid, the p = 2 MMD observation-prediction surrogate predicts the mean, a choice the authors say works reasonably well because transitions are deterministic and observation stochasticity comes from the initial configuration.They caution that this choice may not work well for environments with truly stochastic observations.Source: §7.3 · pp. 51, 53
• AIS-based PORL reaches better performance in most MiniGrid environments, but fails on Lava Crossing while LSTM+PPO fails on larger Key Crossing and Obstructed Maze tasks.The high-dimensional comparison uses five random seeds.Source: Figure 7 · pp. 52–53, §7.3 · p. 53

• An information state yields a dynamic programming decomposition, and simplified decompositions from prior work can be viewed as specific information states.The paper gives two equivalent information-state definitions: one based on predicting the next value, and another based on recursive updating and predicting the next observation.Source: §8 · p. 54
• An AIS approximately satisfies information-state properties and supports approximately optimal planning with error bounded by its one-step approximation errors.The framework also extends to observation and action compression and multi-agent systems, and encompasses existing approximation approaches for fully and partially observed settings.Source: §8 · p. 54
• AIS properties can be estimated from data, enabling policy-gradient algorithms to learn an AIS representation and a policy or action-value function using multi-timescale stochastic gradient descent.Source: §8 · p. 54
• AIS-based PORL algorithms outperform a state-of-the-art baseline in most cases across small-, medium-, and large-scale partially observed problems.Source: §8 · p. 54
• The paper focuses on the simplest algorithm classes; AIS-based value-based methods such as Q-learning, DQN, and DDQN are proposed as extensions.The authors also note that AIS representations include a system model and could serve in model-based methods such as Dyna.Source: §8 · p. 54

A. Comparison with the results of Abel et al. (2016) for state aggregation in MDPs

• Theorem 27's bound for this model is stronger than the bound derived by Abel et al. (2016) by a factor of O(1/(1 − γ)).Source: A. Comparison with the results of Abel… · p. 66
• The selected Abel et al. (2016) model, approximate model similarity, makes the aggregation an (ε, ε|S_hat|)-AIS in total variation.Source: A. Comparison with the results of Abel… · pp. 66–67
• Proposition 38's bound is tighter than Proposition 36's by a factor of 1/(1 − γ).Source: A. Comparison with the results of Abel… · p. 68

B. Comparison with the results of Gelada et al. (2019) for latent space models for MDPs

• A latent-space model with embedding φ is an (ε, δ)-AIS under the Kantorovich distance.The model consists of an embedding, latent transition dynamics, and a latent reward function.Source: B. Comparison with the results of… · pp. 68–69
• When γLp < 1, the value-function Lipschitz bound yields ρF(V) ≤ Lr/(1 − γLp) for the Kantorovich distance.The latent MDP is assumed to be Lipschitz in reward and transition, with constants Lr and Lp.Source: B. Comparison with the results of… · pp. 68–69
• The AIS bound gives the same approximation bound as the latent-space result of Gelada et al. (2019).The paper states that the bounds in Propositions 40 and 43 are exactly the same.Source: B. Comparison with the results of… · p. 69

C. Comparison with the results of Francois-Lavet et al. (2019) for belief approximation in POMDPs

• The AIS comparison concerns belief approximations for infinite-horizon finite-state, finite-action POMDPs with discount factor γ.The cited ε-sufficient-statistic formulation defines an MDP over belief distributions and uses the underlying POMDP kernel.Source: C. Comparison with the results of… · p. 70
• An ε-sufficient statistic yields an AIS, and its prediction-kernel approximation satisfies dF(µt, νt) ≤ 3ε.The construction uses total variation for the statistic space and a bounded-Lipschitz metric for distributions over that space.Source: C. Comparison with the results of… · pp. 70, 71, 73
• The AIS-based bound is tighter than Francois-Lavet et al. (2019)'s bound by a factor of 1/(1 − γ).The paper also describes the improvement as a factor of O(1/(1 − γ)).Source: C. Comparison with the results of… · pp. 70, 74

D. Comparison with the results of Chandak et al. (2020) on lifelong learning for time-varying action spaces

• When newly available actions are quantized, the action quantizer has zero reward error and transition error δ = ρηk.The setup assumes rewards do not depend on the action and uses a ρ-Lipschitz transition kernel.Source: D. Comparison with the results of… · pp. 74–75
• Under symmetric rewards in [−Rmax, Rmax], the paper's action-quantization bound matches Chandak et al. (2020)'s result.The action set grows in discrete stages as the agent becomes aware of additional actions.Source: D. Comparison with the results of… · pp. 74–75
• When the action representation map is unknown, the paper treats the latent-action representation as compression of the quantized action set.The resulting quantizer has zero reward error and transition error ρηk + ζk.Source: D. Comparison with the results of… · pp. 75–76
• For the unknown-map case, the resulting bound matches Chandak et al. (2020)'s under symmetric rewards in [−Rmax, Rmax].The paper compares Proposition 54 with Chandak et al. (2020)'s Proposition 52.Source: D. Comparison with the results of… · pp. 75–76

E. Convergence of the PORL algorithm

• The state-estimator iteration converges almost surely to a state estimator minimizing its loss.This convergence is stated under Assumptions 2 and 3.Source: E. Convergence of the PORL algorithm · p. 77
• The critic iteration converges almost surely to a critic minimizing the stated error.The theorem's proof combines stochastic-approximation results across the learning timescales.Source: E. Convergence of the PORL algorithm · p. 77
• The actor iteration converges almost surely to a local maximum of J(¯ξ∗, ζ∗, θ).The guarantee relies on the regularity conditions in Assumptions 2 and 3.Source: E. Convergence of the PORL algorithm · pp. 76–77

F. Details about the network architecture, training, and hyperparameters

• The AIS generator comprises history compression, AIS updating, reward prediction, and observation prediction.The policy is also modeled as a feed-forward neural network.Source: F. Details about the network… · p. 78
• An LSTM models history compression, with its memory update unit serving as the AIS update function.Source: F. Details about the network… · p. 78
• Feed-forward neural networks model reward prediction, observation prediction, and the policy.Source: F. Details about the network… · p. 78

F.1 Details for low dimensional environments:

• The AIS dimension is 40; the AIS-loss weight λ is 0.0001 for KL and 0.001 for MMD.Source: §F.1 · p. 78
• Training uses 200 samples per batch and 10^5 batches.Source: §F.1 · p. 79
• The AIS learning rate is ADAM(0.003), while policy learning rates are ADAM(0.0006) for KL and ADAM(0.0008) for MMD.Source: §F.1 · p. 79
• Evaluation occurs every 500 batches using 50 rollouts, and CheeseMaze uses the standard environment discount factor.Source: §F.1 · pp. 78–79

F.2 Details for moderate dimensional environments:

• The AIS dimension is 128; the AIS-loss weight λ is 0.0001 for KL and 0.001 for MMD.Source: §F.2 · p. 79
• Training uses 200 samples per batch and 10^5 batches.Source: §F.2 · p. 79
• The AIS learning rate is ADAM(0.003), and the policy learning rate is ADAM(0.0007).Source: §F.2 · p. 80
• Evaluation occurs every 500 batches using 100 rollouts.Source: §F.2 · p. 80

F.3 Details for high dimensional environments:

• High-dimensional minigrid observations are vectors of size 147, representing a 7 × 7 grid with three channels.Source: §F.3 · p. 80
• The high-dimensional setup uses a basic autoencoder with latent dimension 64 and an AIS dimension of 128; the KL variant uses five GMM components.Source: §F.3 · p. 80
• The AIS model is trained with 200 samples per batch; selected environments use 2 × 10^5 batches and others use 10^5.Source: §F.3 · p. 81

F.4 Details for PPO with LSTM and Critic:

• PPO uses 64 parallel actors, 1,280 samples per batch, four epochs per batch, and trajectory recurrence length 20.Source: §F.4 · p. 82

F.5 Details about hyperparameter tuning

• Performance was sensitive to AIS and policy learning rates in most environments; larger AIS sizes generally improved or preserved performance, but sometimes increased training instability.Source: §F.5 · p. 83
• The tested ReLU-versus-Tanh choice did not appear to significantly affect performance in the considered environments.Source: §F.5 · p. 83