In long-horizon autonomy, a robot must make coherent decisions across extended time intervals (minutes, hours, or even days), under partial observability and model uncertainty. A canonical formalization is a partially observable Markov decision process (POMDP) with horizon \( H \), where the robot has access only to noisy observations \( o_t \) and must maintain some form of internal memory to act effectively.

Let \( x_t \) be the (hidden) system state, \( u_t \) the control input, and \( o_t \) the observation at discrete time \( t \). The robot dynamics and observation processes are modeled as

\[ x_{t+1} \sim p(x_{t+1} \mid x_t, u_t), \qquad o_t \sim p(o_t \mid x_t). \]

For a given policy \( \pi \), the long-horizon cost starting from an initial distribution over states is

\[ J_H^{\pi} = \mathbb{E}\!\left[ \sum_{t=0}^{H-1} \gamma^t c(x_t, u_t) \right], \]

where \( \gamma \in (0,1] \) is a discount factor and \( c(x_t,u_t) \) is an instantaneous cost. When \( H \) is large and the robot is partially observable, purely reactive policies \( \pi(u_t \mid o_t) \) are insufficient; the robot must condition on a history

\[ h_t = (o_0, u_0, o_1, u_1, \dots, o_t), \]

or on a compressed internal representation of it.

We therefore introduce an internal memory state \( m_t \), updated recursively, that serves as a sufficient statistic of the past for decision-making. The memory-augmented policy is then of the form \( \pi(u_t \mid m_t) \).

flowchart TD
  O["Observations o_t"] --> M["Internal memory m_t"]
  M --> P["Policy pi(u_t | m_t)"]
  P --> U["Control commands u_t"]
  U --> E["Environment dynamics"]
  E --> O
  M --> L["Long-horizon objectives J_H"]
        

The central questions in this lesson are:

• How should \( m_t \) be defined mathematically?
• How does memory modify Bellman equations and value functions?
• How do we implement such memory in concrete robotic systems, from embedded code to high-level learning libraries?

A POMDP is given by a tuple \( (\mathcal{X},\mathcal{U},\mathcal{O},p,p_o,c,\gamma,H) \). Under partial observability, it is known from POMDP theory that the belief over states, \( b_t(x) = p(x_t = x \mid h_t) \), is a sufficient statistic for optimal control in the sense that an optimal policy exists of the form \( \pi^{\star}(u_t \mid b_t) \).

We can regard the internal memory as an abstract state \( m_t \) which evolves deterministically from history via some update map \( \Phi \). For belief-based memory, this update is the Bayesian filter:

\[ b_{t+1}(x') = \eta \, p(o_{t+1} \mid x') \sum_{x \in \mathcal{X}} p(x' \mid x, u_t) \, b_t(x), \]

where \( \eta \) is a normalization constant. In a continuous state space, the sum is replaced by an integral.

More generally, let \( m_t \) be any (possibly approximate) encoding of history with deterministic update

\[ m_{t+1} = \Phi(m_t, u_t, o_{t+1}), \]

and suppose the memory-augmented policy is

\[ \pi_{\theta}(u_t \mid m_t). \]

We can then treat the pair \( (x_t,m_t) \) as an augmented Markov state of a fully observable MDP, with transition kernel

\[ \tilde{p}\big((x_{t+1},m_{t+1}) \mid (x_t,m_t),u_t\big) = p(x_{t+1} \mid x_t, u_t)\; \sum_{o_{t+1} \in \mathcal{O}} p(o_{t+1} \mid x_{t+1}) \, \delta\!\big(m_{t+1} - \Phi(m_t,u_t,o_{t+1})\big), \]

where \( \delta \) is a Dirac measure (or Kronecker delta in discrete spaces). The cost function depends only on \( x_t,u_t \), so we define

\[ \tilde{c}((x_t,m_t),u_t) = c(x_t,u_t). \]

The value function of a memory-augmented policy \( \pi \) over horizon \( H \) is then

\[ V_H^{\pi}(m_0) = \mathbb{E}\!\left[ \sum_{t=0}^{H-1} \gamma^t c(x_t,u_t) \;\middle|\; m_0 \right], \]

where the expectation is taken with respect to the joint process \( (x_t,m_t,u_t,o_t) \) induced by \( \pi \).

Proposition (Belief optimality). If \( m_t = b_t \) (exact belief), then there exists an optimal policy \( \pi^{\star} \) such that \( \pi^{\star}(u_t \mid h_t) = \pi^{\star}(u_t \mid b_t) \).

Sketch of proof. The belief updates deterministically from \( (b_t, u_t, o_{t+1}) \). The joint process \( (b_t)_{t \ge 0} \) is Markov. Any policy depending on complete histories can be projected to a policy depending only on beliefs without changing the distribution over states and actions; hence, an optimal policy in belief space exists.

Given an augmented state \( (x_t,m_t) \), we can write Bellman equations at the level of memory. Let \( V_t(m_t) \) denote the optimal cost-to-go at time \( t \) when the internal memory is \( m_t \) and the physical state distribution is encoded in it (e.g., via belief). Then

\[ V_t(m_t) = \min_{u_t \in \mathcal{U}} \mathbb{E}\!\left[ c(x_t,u_t) + \gamma V_{t+1}(m_{t+1}) \,\middle|\, m_t, u_t \right], \]

with terminal condition \( V_H(\cdot) = 0 \). The expectation expands over \( x_t,x_{t+1},o_{t+1} \). In the fully belief-based case:

\[ \mathbb{E}\!\left[ c(x_t,u_t) \mid b_t \right] = \sum_{x \in \mathcal{X}} b_t(x)\,c(x,u_t), \]

and the distribution of \( b_{t+1} \) is determined by the Bayesian filter. Thus, solving a POMDP exactly corresponds to dynamic programming in belief space, which is usually intractable for high-dimensional robots.

In practice, we often use approximate memory \( m_t \) (e.g., a finite window of recent observations or the hidden state of a recurrent neural network). In this case, the Bellman equation becomes an approximation, and the optimality guarantees are lost, but computational feasibility is restored.

We can also analyze the effect of horizon truncation. For an infinite horizon discounted problem with value function \( V^{\pi} \), the truncated horizon value with terminal zero satisfies the bound

\[ \big\lvert V^{\pi}(m_0) - V_H^{\pi}(m_0) \big\rvert \le \frac{\gamma^H}{1-\gamma} \, C_{\max}, \]

where \( C_{\max} = \sup_{x,u} \lvert c(x,u) \rvert \). This highlights that, for \( \gamma \approx 1 \), very long horizons are required to control truncation error.

One powerful way to cope with long horizons is to introduce temporal abstraction via options (macro-actions). An option \( \omega \) is defined by:

• An initiation set \( \mathcal{I}_{\omega} \subseteq \mathcal{X} \).
• A low-level policy \( \mu_{\omega}(u \mid x) \).
• A termination condition \( \beta_{\omega}(x) \in [0,1] \).

Executing an option from state \( x_t \) produces a random duration \( K \) and a sequence of states and actions until termination at \( x_{t+K} \). The high-level control problem becomes a semi-Markov decision process (SMDP) with value function

\[ Q^{\pi}(x,\omega) = \mathbb{E}\!\left[ \sum_{k=0}^{K-1} \gamma^k c(x_{t+k},u_{t+k}) + \gamma^K V^{\pi}(x_{t+K}) \,\middle|\, x_t = x, \omega_t = \omega \right], \]

and high-level Bellman equation

\[ V^{\pi}(x) = \sum_{\omega} \pi(\omega \mid x) Q^{\pi}(x,\omega). \]

In the context of long-horizon autonomy, options can be interpreted as high-level skills (e.g., “navigate to room A”, “grasp an object”) whose execution may internally use memory over tens of time steps, while the high-level planner reasons at a slower temporal scale. Memory can thus be architected at multiple levels:

• Short-term memory inside options (local, reactive adaptation).
• Long-term memory at the task level (progress, visited locations).

The design of such multi-scale memory systems is an active research frontier in robotics.

When policies are parameterized by recurrent networks, memory appears as a hidden state \( h_t \) evolving as

\[ h_{t+1} = f_{\theta}(h_t, o_{t+1}), \qquad u_t \sim \pi_{\theta}(u_t \mid h_t). \]

The objective is to minimize \( J_H^{\pi_{\theta}} \). A policy-gradient estimator takes the form

\[ \nabla_{\theta} J_H^{\pi_{\theta}} = \mathbb{E}\!\left[ \sum_{t=0}^{H-1} \nabla_{\theta} \log \pi_{\theta}(u_t \mid h_t) \, G_t \right], \]

where \( G_t \) is a return estimate (e.g., Monte Carlo return or temporal-difference advantage). Because \( h_t \) itself depends on \( \theta \), gradients must be propagated through time (backpropagation through time, BPTT). For long horizons, this leads to vanishing/exploding gradients, making training difficult.

A common approximation is to truncate BPTT to some window \( W \). Let \( t_0 = \max\{0, t-W\} \). The truncated gradient at time \( t \) ignores contributions from steps earlier than \( t_0 \), effectively assuming that the memory state at \( t_0 \) is fixed with respect to \( \theta \). This induces a bias that generally grows as \( H \) increases relative to \( W \), reflecting the challenge of long-horizon credit assignment.

Designing memory architectures with better credit assignment properties (e.g., gated recurrent units, attention mechanisms, or external-addressable memories) is closely tied to achieving robust long-horizon autonomy.

We illustrate a minimal Python implementation of a recurrent policy for a 1D robot with noisy observations. The robot moves on a line according to \( x_{t+1} = x_t + \Delta t\,u_t + w_t \), with noisy observations \( o_t = x_t + v_t \). The goal is to reach a distant target while keeping control effort small.

import numpy as np

# Simple 1D environment with long horizon
class LongHorizon1DEnv:
    def __init__(self, dt=0.1, horizon=200, x0=0.0, x_target=10.0,
                 process_std=0.01, obs_std=0.05):
        self.dt = dt
        self.H = horizon
        self.x_target = x_target
        self.proc_std = process_std
        self.obs_std = obs_std
        self.reset(x0)

    def reset(self, x0=0.0):
        self.t = 0
        self.x = float(x0)
        o = self.x + np.random.randn() * self.obs_std
        return o

    def step(self, u):
        # Dynamics
        w = np.random.randn() * self.proc_std
        self.x = self.x + self.dt * float(u) + w
        # Observation
        o = self.x + np.random.randn() * self.obs_std
        # Cost: squared position error + quadratic control
        pos_err = self.x - self.x_target
        cost = pos_err**2 + 0.01 * float(u)**2
        self.t += 1
        done = (self.t >= self.H)
        return o, -cost, done, {}

# Recurrent policy with explicit hidden state (memory)
class RNNPolicy:
    def __init__(self, obs_dim=1, hidden_dim=16, u_max=1.0):
        self.obs_dim = obs_dim
        self.hidden_dim = hidden_dim
        self.u_max = u_max
        # Parameters: simple tanh RNN + linear output
        rng = np.random.default_rng(0)
        self.Wxh = rng.normal(scale=0.1, size=(hidden_dim, obs_dim))
        self.Whh = rng.normal(scale=0.1, size=(hidden_dim, hidden_dim))
        self.bh = np.zeros((hidden_dim, 1))
        self.Why = rng.normal(scale=0.1, size=(1, hidden_dim))
        self.by = np.zeros((1, 1))
        self.h = np.zeros((hidden_dim, 1))  # memory state

    def reset_hidden(self):
        self.h[:] = 0.0

    def forward(self, o):
        # o: scalar observation
        obs = np.array([[float(o)]])
        self.h = np.tanh(self.Wxh @ obs + self.Whh @ self.h + self.bh)
        u = self.Why @ self.h + self.by
        # Squash to control limits
        u = np.clip(u, -self.u_max, self.u_max)
        return float(u)

# Rollout with fixed (untrained) parameters to illustrate memory usage
if __name__ == "__main__":
    env = LongHorizon1DEnv()
    policy = RNNPolicy()
    num_episodes = 3

    for ep in range(num_episodes):
        o = env.reset(x0=0.0)
        policy.reset_hidden()
        total_return = 0.0
        for t in range(env.H):
            u = policy.forward(o)
            o, r, done, info = env.step(u)
            total_return += r
            if done:
                break
        print(f"Episode {ep}, total return (untrained): {total_return:.2f}")
      

In a full implementation, one would add a policy-gradient or actor-critic algorithm that backpropagates gradients through the hidden state \( h_t \) to learn memory-dependent behavior that solves the long-horizon task.

In classical control, long-horizon autonomy is often handled using receding-horizon (MPC) strategies. We still need memory to store recent observations or estimates. Below is a simplified C++ sketch of a 1D MPC-like controller with an explicit ring buffer for storing the last \( W \) observations and controls. Libraries such as Eigen (for linear algebra) and roscpp (for ROS integration) are typical in robotic implementations.

#include <iostream>
#include <array>
#include <cmath>

// Simple ring buffer for fixed-size memory
template <typename T, std::size_t W>
class RingBuffer {
public:
    RingBuffer() : idx_(0), full_(false) {
        data_.fill(T());
    }

    void push(const T& value) {
        data_[idx_] = value;
        idx_ = (idx_ + 1) % W;
        if (idx_ == 0) {
            full_ = true;
        }
    }

    // Access i-th most recent element (i = 0 is latest)
    T get(std::size_t i) const {
        if (i >= size()) {
            return data_[0];
        }
        std::size_t pos = (idx_ + W - 1 - i) % W;
        return data_[pos];
    }

    std::size_t size() const {
        return full_ ? W : idx_;
    }

private:
    std::array<T, W> data_;
    std::size_t idx_;
    bool full_;
};

struct StateEstimate {
    double x;      // position
    double v;      // velocity (optional)
};

double stageCost(double x, double u, double x_target) {
    double pos_err = x - x_target;
    return pos_err * pos_err + 0.01 * u * u;
}

// Very simple receding-horizon lookahead with heuristic control sequence
double computeOptimalControl(const StateEstimate& x_hat,
                             const RingBuffer<StateEstimate, 32>& memory,
                             double x_target,
                             std::size_t horizon_steps,
                             double dt) {
    // Here we use a crude heuristic: proportional feedback using
    // an estimate that might depend on memory (not shown in detail).
    (void)memory; // in a real system, use past data to refine estimate
    double Kp = 0.5;
    double u = -Kp * (x_hat.x - x_target);
    // Clip control
    if (u > 1.0) u = 1.0;
    if (u < -1.0) u = -1.0;
    return u;
}

int main() {
    constexpr std::size_t W = 32;
    RingBuffer<StateEstimate, W> mem;

    StateEstimate x_hat{0.0, 0.0};
    double x_target = 10.0;
    double dt = 0.1;
    std::size_t H = 200;

    for (std::size_t t = 0; t < H; ++t) {
        // In practice, x_hat would come from an observer (e.g., Kalman filter)
        // that itself uses the memory buffer 'mem'.
        mem.push(x_hat);

        double u = computeOptimalControl(x_hat, mem, x_target, 20, dt);

        // Simulate simple dynamics x_{t+1} = x_t + dt * u
        x_hat.x += dt * u;

        std::cout << "t=" << t <<
                     " x_hat=" << x_hat.x <<
                     " u=" << u << std::endl;
    }
    return 0;
}
      

Even though this example uses a simple heuristic controller, the RingBuffer abstraction illustrates how an explicit memory structure can be introduced and used in MPC-style long-horizon control loops.

Java-based robotics stacks (or middleware extensions) often maintain history buffers to support long-horizon decision logic. The code below sketches a finite-window memory of the last \( W \) poses and a simple long-horizon progress metric.

import java.util.ArrayDeque;
import java.util.Deque;

class Pose2D {
    public double x;
    public double y;
    public double theta;

    public Pose2D(double x, double y, double theta) {
        this.x = x;
        this.y = y;
        this.theta = theta;
    }
}

class PoseMemory {
    private final int windowSize;
    private final Deque<Pose2D> buffer;

    public PoseMemory(int windowSize) {
        this.windowSize = windowSize;
        this.buffer = new ArrayDeque<>(windowSize);
    }

    public void addPose(Pose2D pose) {
        if (buffer.size() == windowSize) {
            buffer.removeFirst();
        }
        buffer.addLast(pose);
    }

    public Pose2D getMostRecent() {
        return buffer.peekLast();
    }

    public Pose2D getOldest() {
        return buffer.peekFirst();
    }

    public int size() {
        return buffer.size();
    }
}

class LongHorizonNavigator {
    private final PoseMemory memory;
    private final double goalX;
    private final double goalY;

    public LongHorizonNavigator(int windowSize, double goalX, double goalY) {
        this.memory = new PoseMemory(windowSize);
        this.goalX = goalX;
        this.goalY = goalY;
    }

    public void update(Pose2D currentPose) {
        memory.addPose(currentPose);
    }

    // Simple long-horizon progress metric using oldest vs newest pose
    public double computeProgress() {
        if (memory.size() < 2) {
            return 0.0;
        }
        Pose2D oldest = memory.getOldest();
        Pose2D newest = memory.getMostRecent();
        double dOld = distance(oldest.x, oldest.y, goalX, goalY);
        double dNew = distance(newest.x, newest.y, goalX, goalY);
        return dOld - dNew; // positive if we moved closer
    }

    private static double distance(double x1, double y1, double x2, double y2) {
        double dx = x1 - x2;
        double dy = y1 - y2;
        return Math.sqrt(dx * dx + dy * dy);
    }
}

public class LongHorizonDemo {
    public static void main(String[] args) {
        LongHorizonNavigator nav = new LongHorizonNavigator(50, 10.0, 0.0);
        for (int t = 0; t < 100; ++t) {
            // Fake pose updates along x-axis
            Pose2D pose = new Pose2D(0.1 * t, 0.0, 0.0);
            nav.update(pose);
            double progress = nav.computeProgress();
            System.out.println("t=" + t + " progress=" + progress);
        }
    }
}
      

This example demonstrates a finite-window memory that supports long-horizon reasoning, such as estimating whether the robot is converging to a goal or stuck in a local minimum.

In MATLAB/Simulink, long-horizon autonomy is often realized using Model Predictive Control (MPC) blocks combined with observers (e.g., Kalman filters). Below is a MATLAB script that sets up a simple linear MPC problem with horizon \( H \) and a discrete-time state-space model, which can then be embedded in a Simulink model using the MPC and State-Space blocks.

% Discrete-time linear model x_{k+1} = A x_k + B u_k, y_k = C x_k
A = [1.0 0.1; 0 1.0];
B = [0.0; 0.1];
C = [1 0];
Ts = 0.1;

sys = ss(A, B, C, 0, Ts);

% Prediction horizon and control horizon
Hp = 40;   % prediction length (long horizon)
Hc = 10;   % control horizon

mpcobj = mpc(sys, Ts, Hp, Hc);

% Weights: position tracking vs control effort
mpcobj.Weights.OutputVariables = 1;
mpcobj.Weights.ManipulatedVariablesRate = 0.01;

% Constraints on control input
mpcobj.MV.Min = -1;
mpcobj.MV.Max =  1;

% Reference trajectory (long-horizon step to x = 10)
Tfinal = 20;
r = ones(Tfinal / Ts, 1) * 10;  % desired position

% Simulate in MATLAB
x0 = [0; 0];
mpcstate = mpcstate(mpcobj);
x = x0;
Y = [];
U = [];
for k = 1:length(r)
    y = C * x;
    u = mpcmove(mpcobj, mpcstate, y, r(k));
    x = A * x + B * u;
    Y(end+1,1) = y; %#ok<AGROW>
    U(end+1,1) = u; %#ok<AGROW>
end

% Plot results
figure;
subplot(2,1,1);
plot(0:Ts:(length(Y)-1)*Ts, Y, 'LineWidth', 1.5);
hold on; plot(0:Ts:(length(r)-1)*Ts, r, '--');
xlabel('Time [s]'); ylabel('Position');
title('Long-horizon tracking with MPC');

subplot(2,1,2);
plot(0:Ts:(length(U)-1)*Ts, U, 'LineWidth', 1.5);
xlabel('Time [s]'); ylabel('Control input');
title('MPC control effort');

% The corresponding Simulink model can include:
% - "State-Space" block with matrices A, B, C, 0
% - "MPC Controller" block using mpcobj
% - Measurement noise and reference generator blocks
      

Here the internal state of the MPC controller and its observer acts as a structured memory that allows consistent long-horizon tracking in the presence of noise and constraints.

We now sketch a finite-horizon dynamic programming solution in Wolfram Mathematica where the state includes a scalar physical state and a discrete memory bit indicating whether the robot has visited a certain region. This illustrates how memory can be explicitly modeled in the state.

(* State: {x, m}, where x is position on a grid and m in {0,1}
   indicates whether a special region has been visited. *)

ClearAll["Global`*"];

states = Flatten[
   Table[{x, m}, {x, -5, 5}, {m, 0, 1}], 1
];

actions = {-1, 0, 1}; (* move left, stay, move right *)

gamma = 0.95;
H = 10;

(* Cost: penalize distance from goal and encourage visiting region *)
goal = 3;
specialRegion = {-1, 0}; (* x in [-1,0] *)

cost[{x_, m_}, u_] := Module[{xNext},
  xNext = x + u;
  (* Memory update: mNext = 1 if we enter special region *)
  0.1*(xNext - goal)^2 + 0.5*(1 - m)
];

transition[{x_, m_}, u_] := Module[{xNext, mNext},
  xNext = Max[Min[x + u, 5], -5];
  mNext = If[-1 <= xNext <= 0, 1, m];
  {xNext, mNext}
];

(* Initialize terminal value function *)
V = Association[];
Do[
  V[{x, m, H}] = 0.0,
  {x, -5, 5}, {m, 0, 1}
];

(* Backward dynamic programming over horizon *)
Do[
  Do[
    Module[{bestVal = Infinity, bestAct = 0.0},
      Do[
        Module[{sNext, qVal},
          sNext = transition[{x, m}, u];
          qVal = cost[{x, m}, u] + gamma * V[Append[sNext, t + 1]];
          If[qVal < bestVal,
            bestVal = qVal;
            bestAct = u;
          ];
        ],
        {u, actions}
      ];
      V[{x, m, t}] = bestVal;
      ,
      {m, 0, 1}
    ],
    {x, -5, 5}
  ],
  {t, H - 1, 0, -1}
];

(* Example: optimal cost-to-go from x=0, m=0 at time 0 *)
V[{0, 0, 0}]
      

This small example shows explicitly how the memory bit \( m \) augments the state space to encode information about past events that matter for future rewards.

Problem 1 (Belief as Sufficient Memory). Consider a POMDP with finite state space \( \mathcal{X} \), action space \( \mathcal{U} \), observation space \( \mathcal{O} \), and horizon \( H \). Define the belief \( b_t(x) = p(x_t = x \mid h_t) \). Prove that, for any history-dependent policy \( \pi(u_t \mid h_t) \), there exists a belief-based policy \( \tilde{\pi}(u_t \mid b_t) \) that induces the same joint distribution over trajectories \( (x_0,u_0,\dots,x_H) \).

Solution. Let a history-dependent policy \( \pi(u_t \mid h_t) \) be given. Fix any time \( t \) and belief \( b_t \). This belief corresponds to an equivalence class of histories with the same conditional distribution over states. Define

\[ \tilde{\pi}(u_t \mid b_t) := \mathbb{E}\!\left[ \pi(u_t \mid h_t) \,\middle|\, b_t \right], \]

where the expectation is taken over histories \( h_t \) consistent with \( b_t \). Consider the joint distribution

\[ p_{\pi}(x_0,u_0,\dots,x_H) = p(x_0) \prod_{t=0}^{H-1} \sum_{h_t} p(h_t \mid x_0,\dots,x_t,u_0,\dots,u_{t-1}) \,\pi(u_t \mid h_t) \,p(x_{t+1} \mid x_t,u_t). \]

Replacing \( \pi(u_t \mid h_t) \) by its conditional expectation conditioned on \( b_t \) does not change this distribution because, conditioned on \( (x_0,\dots,x_t,u_0,\dots,u_{t-1}) \), \( h_t \) is a deterministic function and \( b_t \) is a deterministic function of \( h_t \). Thus, \( p_{\pi} = p_{\tilde{\pi}} \), showing that a belief-based policy can reproduce any history-dependent policy at the level of trajectory distributions.

Problem 2 (Horizon Truncation Error Bound). Suppose \( \lvert c(x,u) \rvert \le C_{\max} \) and consider the infinite-horizon discounted cost \( J^{\pi} = \mathbb{E}[\sum_{t=0}^{\infty} \gamma^t c_t] \) and the truncated cost \( J_H^{\pi} = \mathbb{E}[\sum_{t=0}^{H-1} \gamma^t c_t] \). Derive the bound

\[ \lvert J^{\pi} - J_H^{\pi} \rvert \le \frac{\gamma^H}{1-\gamma} C_{\max}. \]

Solution. We have

\[ J^{\pi} - J_H^{\pi} = \mathbb{E}\!\left[ \sum_{t=H}^{\infty} \gamma^t c_t \right]. \]

Taking absolute values and using the triangle inequality,

\[ \lvert J^{\pi} - J_H^{\pi} \rvert \le \mathbb{E}\!\left[ \sum_{t=H}^{\infty} \gamma^t \lvert c_t \rvert \right] \le \sum_{t=H}^{\infty} \gamma^t C_{\max} = C_{\max} \frac{\gamma^H}{1-\gamma}, \]

which proves the claimed bound.

Problem 3 (Markov Property of Augmented State). Let the internal memory evolve as \( m_{t+1} = \Phi(m_t, u_t, o_{t+1}) \). Show that the augmented state \( (x_t,m_t) \) is Markov with respect to the control sequence \( u_t \).

Solution. We need to show that

\[ p(x_{t+1},m_{t+1} \mid x_0,m_0,u_0,\dots,x_t,m_t,u_t) = p(x_{t+1},m_{t+1} \mid x_t,m_t,u_t). \]

By the system model, \( x_{t+1} \) depends only on \( x_t,u_t \), and \( o_{t+1} \) depends only on \( x_{t+1} \). The memory update uses only \( (m_t,u_t,o_{t+1}) \). Thus

\[ p(x_{t+1},m_{t+1} \mid \text{history}) = \sum_{o_{t+1}} p(o_{t+1} \mid x_{t+1}) p(x_{t+1} \mid x_t,u_t) \delta\!\big(m_{t+1} - \Phi(m_t,u_t,o_{t+1})\big), \]

which depends only on \( (x_t,m_t,u_t) \), establishing the Markov property.

Problem 4 (Finite-Window Memory as Approximate Belief). Consider a POMDP in which the observation process is \( k \)-step observable, meaning that the last \( k \) observations uniquely determine the state. Show that if \( k \le W \), then a sliding window memory of size \( W \) is sufficient for optimal control.

Solution. If the process is \( k \)-step observable, then the mapping

\[ g : (o_{t-k+1},\dots,o_t) \mapsto x_t \]

is invertible. With a window \( W \ge k \), the last \( k \) observations are always contained in memory. Therefore, the memory \( m_t \) can be used to reconstruct \( x_t \) exactly, and the problem reduces to a fully observable MDP in \( x_t \), where a Markov policy \( \pi(u_t \mid x_t) \) is optimal. The memory policy \( \tilde{\pi}(u_t \mid m_t) = \pi(u_t \mid g(\text{last }k \text{ observations})) \) is thus optimal.

Problem 5 (Conceptual Flow for Long-Horizon Autonomy). Sketch a decision flow for designing a long-horizon autonomous system in a partially observable environment, starting from task specification and ending at a memory-augmented policy implementation.

Solution (flowchart).

flowchart TD
  S["Task + horizon specification"] --> U["Uncertainty + observability analysis"]
  U --> M1["Choose memory representation (belief, window, RNN state)"]
  M1 --> P1["Select planning framework (MPC, RL, TAMP)"]
  P1 --> D["Design value / cost structure"]
  D --> I["Implement memory update + policy"]
  I --> E["Evaluate long-horizon performance"]
  E --> R["Refine memory, horizon, and abstraction"]
        

In this lesson we formalized long-horizon autonomy as decision-making over POMDPs with large horizons and emphasized the central role of internal memory. We showed how memory-augmented policies can be analyzed via augmented-state Bellman equations, how truncating the horizon introduces bounded error, and how temporal abstraction (options) can mitigate computational burdens. We then connected these abstractions to concrete implementations in Python, C++, Java, MATLAB/Simulink, and Wolfram Mathematica, highlighting the interplay between algorithmic design and systems-level memory structures in advanced robotic autonomy.