F.Markov — Cost of Memoryless Inference Under Partial Observability¶
Area 01 · Decision-Making Under Uncertainty — F-Series Foundational Experiments
Historical thesis tested: The Markov property holds for the BELIEF STATE: bₜ is a sufficient statistic for the full history, making the belief MDP Markovian. A BeliefAgent that conditions on bₜ is therefore already acting on a Markov state — it is NOT discarding the Markov property, it is exploiting it.
This notebook asks: When an agent acts on only the most recent observation oₜ (ignoring history), how much does this MEMORYLESS approximation cost in decision quality? And at what history depth k does performance recover to near-optimal?
Terminology:
- "Memoryless inference": acting on oₜ alone, as if oₜ=sₜ (MemorylessAgent)
- This is distinct from the Markov property, which is satisfied by bₜ, not oₜ
- The cost we measure is "cost of discarding observation history", not "cost of Markov"
Framework (Area 01): sₜ → oₜ → bₜ → aₜ
- Hidden state: sₜ ∈ {0,1}, switches with probability p_switch per step
- Observation: oₜ = sₜ w.p. p_correct, else 1−sₜ (binary symmetric channel)
- Belief: bₜ(s) = P(sₜ=s | o₀, o₁, …, oₜ) — a Markov state for the POMDP
Agents compared:
- MemorylessAgent — acts directly on oₜ (memoryless; treats observation as state)
- WindowAgent(k) — Bayesian update over last k observations
- BeliefAgent — full posterior bₜ maintained over all history (optimal)
- RandomAgent — uniform baseline
Experiments:
- E01: Baseline cost of memoryless inference (trajectory view)
- E02: History depth k sweep — at what k does performance recover?
- E03: State persistence sweep — when does memory stop helping?
- E04: p_correct × p_switch grid — 2D cost of memoryless inference
- E05: Minimum sufficient memory depth as a function of world dynamics
Imports and configuration¶
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.gridspec as gridspec
from typing import List, Dict, Tuple
np.random.seed(42)
COLORS = {
'belief': '#2563eb', # full posterior — blue
'window_20': '#0284c7', # k=20 — sky
'window_10': '#0891b2', # k=10 — cyan
'window_5': '#16a34a', # k=5 — green
'window_3': '#d97706', # k=3 — orange
'window_2': '#ea580c', # k=2 — orange-red
'memoryless':'#dc2626', # k=1 — red
'random': '#9ca3af', # random — gray
'optimal': '#000000', # reference — black
}
plt.rcParams.update({
'figure.dpi': 120, 'font.size': 10,
'axes.spines.top': False, 'axes.spines.right': False,
'axes.grid': True, 'grid.alpha': 0.3,
})
Environment and agents¶
class TwoDoorEnv:
"""Two-door environment with hidden Markov dynamics.
Hidden state sₜ ∈ {0,1} switches with probability p_switch per step.
Observation oₜ equals sₜ w.p. p_correct, else 1−sₜ.
Reward: +1 if action equals true state, −1 otherwise.
"""
def __init__(self, p_correct: float = 0.8, p_switch: float = 0.1):
assert 0.5 < p_correct <= 1.0, "p_correct must be > 0.5"
assert 0.0 <= p_switch <= 0.5, "p_switch must be in [0, 0.5]"
self.p_correct = p_correct
self.p_switch = p_switch
self.true_state: int = 0
def reset(self) -> int:
"""Initialise random state, return first observation."""
self.true_state = np.random.randint(2)
return self._observe()
def _observe(self) -> int:
return self.true_state if np.random.random() < self.p_correct \
else 1 - self.true_state
def step(self) -> Tuple[int, int]:
"""Advance world (state may switch), return (observation, true_state)."""
if np.random.random() < self.p_switch:
self.true_state = 1 - self.true_state
return self._observe(), self.true_state
class RandomAgent:
def reset(self): pass
def update(self, obs: int): pass
def act(self) -> int: return np.random.randint(2)
class MemorylessAgent:
"""Acts directly on the current observation — memoryless inference.
Treats oₜ as if it were the true state sₜ, discarding all history.
This is NOT the Markov assumption: the belief bₜ is a valid Markov state,
but oₜ is not. Acting on oₜ alone is a memoryless approximation.
Equivalent to WindowAgent(k=1).
"""
_last_obs: int = 0
def reset(self): self._last_obs = 0
def update(self, obs: int): self._last_obs = obs
def act(self) -> int: return self._last_obs
class BeliefAgent:
"""Optimal Bayesian agent maintaining the full posterior P(sₜ | h_t).
Update rule per step:
Predict : b' = b(1−p_switch) + (1−b)p_switch
Update : b = L(o|s=0)·b' / [L(o|s=0)·b' + L(o|s=1)·(1−b')]
"""
def __init__(self, p_correct: float, p_switch: float):
self.p_correct = p_correct
self.p_switch = p_switch
self.belief = 0.5 # P(sₜ=0)
def reset(self):
self.belief = 0.5
def update(self, obs: int):
b = self.belief * (1 - self.p_switch) + (1 - self.belief) * self.p_switch
l0 = self.p_correct if obs == 0 else (1 - self.p_correct)
l1 = (1 - self.p_correct) if obs == 0 else self.p_correct
denom = l0 * b + l1 * (1 - b)
if denom > 1e-12:
self.belief = l0 * b / denom
def act(self) -> int:
return 0 if self.belief >= 0.5 else 1
class WindowAgent:
"""k-step window Bayesian agent.
Maintains the last k observations; recomputes the posterior from a
uniform prior at the start of each window.
k=1 → identical to MemorylessAgent (memoryless inference)
k→∞ → converges to BeliefAgent (full history)
Note: WindowAgent differs from BeliefAgent in one key way — it starts
from a uniform prior at step max(0, t−k), discarding older history.
The approximation error shrinks as k grows or as p_switch increases
(making old history less informative about current state).
"""
def __init__(self, k: int, p_correct: float, p_switch: float):
self.k = k
self.p_correct = p_correct
self.p_switch = p_switch
self.buffer: List[int] = []
self.belief = 0.5
def reset(self):
self.buffer = []
self.belief = 0.5
def update(self, obs: int):
self.buffer.append(obs)
if len(self.buffer) > self.k:
self.buffer.pop(0)
self._recompute()
def _recompute(self):
"""Full Bayesian update over window, starting from uniform prior."""
belief = 0.5
for o in self.buffer:
b = belief * (1 - self.p_switch) + (1 - belief) * self.p_switch
l0 = self.p_correct if o == 0 else (1 - self.p_correct)
l1 = (1 - self.p_correct) if o == 0 else self.p_correct
denom = l0 * b + l1 * (1 - b)
if denom > 1e-12:
belief = l0 * b / denom
self.belief = belief
def act(self) -> int:
return 0 if self.belief >= 0.5 else 1
Shared utilities¶
def run_episode(env: TwoDoorEnv, agent, T: int) -> Tuple[List[float], List[int]]:
"""Run one episode of T steps. Returns (accuracy_per_step, actions)."""
obs = env.reset()
agent.reset()
agent.update(obs)
correct = []
# First step: act on initial observation
action = agent.act()
correct.append(int(action == env.true_state))
for _ in range(T - 1):
obs, true_state = env.step()
agent.update(obs)
action = agent.act()
correct.append(int(action == true_state))
return correct
def run_experiment(env: TwoDoorEnv, agent, T: int, n_episodes: int) -> Dict[str, float]:
"""Aggregate metrics over n_episodes."""
all_correct = np.zeros(T)
for _ in range(n_episodes):
ep = run_episode(env, agent, T)
all_correct += np.array(ep)
accuracy_trajectory = all_correct / n_episodes
mean_accuracy = accuracy_trajectory.mean()
# Performance Retention: PR = J(agent)/J_optimal; J_optimal=1.0 per step
mean_reward = 2 * mean_accuracy - 1 # map [0,1] → [-1,1]
return {
'accuracy': mean_accuracy,
'pr': mean_reward,
'trajectory': accuracy_trajectory,
'disagreement': 1.0 - mean_accuracy,
}
E01 — Baseline cost of memoryless inference¶
Hypothesis: In a partially observable world with persistent state (p_switch < 0.5), the MemorylessAgent (memoryless inference) systematically underperforms the BeliefAgent. The gap is visible in accuracy trajectories: BeliefAgent improves over time as history accumulates, while MemorylessAgent stays flat (no memory to improve from).
Setup: p_correct = 0.8, p_switch = 0.1, T = 100 steps, n_episodes = 5000.
print("E01: Baseline cost of memoryless inference")
print("=" * 50)
E01_P_CORRECT = 0.8
E01_P_SWITCH = 0.1
E01_T = 100
E01_N_EPISODES = 5000
env_e01 = TwoDoorEnv(p_correct=E01_P_CORRECT, p_switch=E01_P_SWITCH)
agents_e01 = {
'BeliefAgent': BeliefAgent(E01_P_CORRECT, E01_P_SWITCH),
'MemorylessAgent': MemorylessAgent(),
'RandomAgent': RandomAgent(),
}
results_e01 = {}
for name, agent in agents_e01.items():
np.random.seed(42)
res = run_experiment(env_e01, agent, E01_T, E01_N_EPISODES)
results_e01[name] = res
print(f" {name:20s} accuracy={res['accuracy']:.4f} PR={res['pr']:.4f}")
markov_cost_e01 = results_e01['BeliefAgent']['accuracy'] \
- results_e01['MemorylessAgent']['accuracy']
print(f"\n Memoryless inference cost: Δaccuracy = {markov_cost_e01:.4f}")
print(f" (MemorylessAgent forfeits {markov_cost_e01*100:.1f}pp of accuracy by discarding observation history)")
# --- Plot ---
fig, axes = plt.subplots(1, 2, figsize=(11, 4))
fig.suptitle("E01 — Baseline Cost of Memoryless Inference\n"
f"p_correct={E01_P_CORRECT}, p_switch={E01_P_SWITCH}", y=1.01)
ax = axes[0]
plot_map = {
'BeliefAgent': ('BeliefAgent (full posterior)', COLORS['belief']),
'MemorylessAgent': ('MemorylessAgent (k=1)', COLORS['memoryless']),
'RandomAgent': ('RandomAgent', COLORS['random']),
}
for name, (label, color) in plot_map.items():
traj = results_e01[name]['trajectory']
ax.plot(range(E01_T), traj, color=color, label=label, lw=1.8)
ax.axhline(0.5, color='black', lw=0.8, ls=':', label='Chance (0.5)')
ax.axhline(E01_P_CORRECT, color='black', lw=0.8, ls='--', label=f'p_correct={E01_P_CORRECT}')
ax.set_xlabel("Step within episode")
ax.set_ylabel("Accuracy (P(action = true state))")
ax.set_title("Accuracy trajectory over episode")
ax.set_ylim(0.45, 1.0)
ax.legend(fontsize=8)
ax = axes[1]
names = ['RandomAgent', 'MemorylessAgent', 'BeliefAgent']
accs = [results_e01[n]['accuracy'] for n in names]
colors_b = [COLORS['random'], COLORS['memoryless'], COLORS['belief']]
bars = ax.bar(names, accs, color=colors_b, width=0.5, edgecolor='white')
for bar, acc in zip(bars, accs):
ax.text(bar.get_x() + bar.get_width()/2, bar.get_height() + 0.005,
f'{acc:.4f}', ha='center', va='bottom', fontsize=9)
ax.axhline(0.5, color='black', lw=0.8, ls=':')
ax.set_ylim(0.4, 1.0)
ax.set_ylabel("Mean accuracy")
ax.set_title(f"Mean accuracy (T={E01_T} steps)")
plt.tight_layout()
plt.savefig('e01_markov_cost_baseline.png', bbox_inches='tight')
plt.close()
print("\nSaved: e01_markov_cost_baseline.png")
FINDING 1: The MemorylessAgent (memoryless inference) achieves accuracy ≈ p_correct = 0.80 — it copies the current observation, which is correct exactly as often as the channel is. The BeliefAgent improves substantially above this baseline by accumulating evidence across steps, exploiting the persistence of the hidden state (p_switch=0.1 means the state typically persists for ~10 steps). The trajectory plot shows BeliefAgent improving over the first ~20 steps as its posterior concentrates, then stabilising at a higher accuracy. Discarding observation history costs approximately Δaccuracy ≈ 0.05–0.08 in this regime. (Note: the BeliefAgent is a Markov agent — it acts on bₜ, which is a sufficient statistic. The cost we observe is not the cost of the Markov property but of discarding history.)
E02 — History depth sweep¶
Hypothesis: Performance increases monotonically with window depth k, recovering to near-optimal at k of order 1/p_switch (the expected state persistence length). For p_switch=0.1, the state persists for ~10 steps on average, so k≈10–15 should close most of the gap to the BeliefAgent.
Setup: p_correct=0.8, p_switch=0.1, k ∈ {1,2,3,5,10,15,20}, T=100, n_episodes=3000.
print("\nE02: History depth sweep")
print("=" * 50)
E02_K_VALUES = [1, 2, 3, 5, 10, 15, 20]
E02_P_CORRECT = 0.8
E02_P_SWITCH = 0.1
E02_T = 100
E02_N_EPISODES = 3000
env_e02 = TwoDoorEnv(p_correct=E02_P_CORRECT, p_switch=E02_P_SWITCH)
results_e02_k = {}
results_e02_full = {}
for k in E02_K_VALUES:
agent = WindowAgent(k, E02_P_CORRECT, E02_P_SWITCH)
np.random.seed(42)
res = run_experiment(env_e02, agent, E02_T, E02_N_EPISODES)
results_e02_k[k] = res
print(f" WindowAgent(k={k:>2}) accuracy={res['accuracy']:.4f} PR={res['pr']:.4f}")
# BeliefAgent benchmark
np.random.seed(42)
res_belief_e02 = run_experiment(env_e02, BeliefAgent(E02_P_CORRECT, E02_P_SWITCH),
E02_T, E02_N_EPISODES)
results_e02_full['belief'] = res_belief_e02
print(f" BeliefAgent (k=∞) accuracy={res_belief_e02['accuracy']:.4f} PR={res_belief_e02['pr']:.4f}")
belief_acc = res_belief_e02['accuracy']
k_recover = next((k for k in E02_K_VALUES
if results_e02_k[k]['accuracy'] >= belief_acc - 0.005), None)
print(f"\n Belief accuracy = {belief_acc:.4f}")
print(f" First k reaching within 0.5pp of belief: k = {k_recover}")
# --- Plot ---
fig, axes = plt.subplots(1, 2, figsize=(11, 4))
fig.suptitle("E02 — History Depth Sweep\n"
f"p_correct={E02_P_CORRECT}, p_switch={E02_P_SWITCH}", y=1.01)
k_colors = {
1: COLORS['memoryless'],
2: COLORS['window_2'],
3: COLORS['window_3'],
5: COLORS['window_5'],
10: COLORS['window_10'],
15: COLORS['window_20'],
20: COLORS['belief'],
}
ax = axes[0]
for k in E02_K_VALUES:
traj = results_e02_k[k]['trajectory']
alpha = 0.5 + 0.5 * (E02_K_VALUES.index(k) / (len(E02_K_VALUES) - 1))
ax.plot(range(E02_T), traj, color=k_colors[k], label=f'k={k}', lw=1.5, alpha=alpha)
ax.plot(range(E02_T), res_belief_e02['trajectory'],
color=COLORS['belief'], lw=2.5, label='Belief (k=∞)', ls='--')
ax.axhline(E02_P_CORRECT, color='black', lw=0.8, ls=':', label=f'p_correct={E02_P_CORRECT}')
ax.set_xlabel("Step within episode")
ax.set_ylabel("Accuracy")
ax.set_title("Accuracy trajectories by window depth k")
ax.set_ylim(0.75, 1.0)
ax.legend(fontsize=7, ncol=2)
ax = axes[1]
k_accs = [results_e02_k[k]['accuracy'] for k in E02_K_VALUES]
ax.plot(E02_K_VALUES, k_accs, 'o-', color=COLORS['memoryless'], lw=2, ms=7, label='WindowAgent(k)')
ax.axhline(belief_acc, color=COLORS['belief'], lw=2, ls='--', label=f'BeliefAgent ({belief_acc:.4f})')
ax.axhline(belief_acc - 0.005, color=COLORS['belief'], lw=1, ls=':', alpha=0.5,
label='Belief − 0.5pp')
if k_recover:
ax.axvline(k_recover, color='#6b7280', lw=1, ls=':', alpha=0.7)
ax.text(k_recover + 0.3, belief_acc - 0.01, f'k={k_recover}', fontsize=8, color='#6b7280')
ax.set_xlabel("Window depth k")
ax.set_ylabel("Mean accuracy (T=100 steps)")
ax.set_title("Accuracy vs window depth")
ax.legend(fontsize=9)
plt.tight_layout()
plt.savefig('e02_history_depth_sweep.png', bbox_inches='tight')
plt.close()
print("Saved: e02_history_depth_sweep.png")
FINDING 2: Performance increases monotonically with k but with diminishing returns. The largest gains come from k=1→2→3: even a 2-step memory substantially improves on the Markov assumption. Performance saturates around k≈10 for these dynamics, consistent with the expected state lifetime of 1/p_switch = 10 steps. Beyond k=10, WindowAgent(k) is essentially indistinguishable from BeliefAgent — the older observations contribute negligible information because the state is unlikely to be the same as it was 10+ steps ago.
E03 — State persistence sweep¶
Hypothesis: The cost of memoryless inference is proportional to state persistence. When p_switch → 0.5 (i.i.d. world), the current observation contains ALL available information about the current state (history is irrelevant), so MemorylessAgent = BeliefAgent. When p_switch → 0 (persistent world), history is highly informative and the memoryless cost grows.
Setup: p_correct=0.8, p_switch ∈ [0.01, 0.48], k=10, T=100, n_episodes=3000.
print("\nE03: State persistence sweep")
print("=" * 50)
E03_P_SWITCH_VALUES = np.linspace(0.01, 0.48, 16)
E03_P_CORRECT = 0.8
E03_T = 100
E03_N_EPISODES = 3000
E03_K = 10
results_e03_memoryless = []
results_e03_belief = []
results_e03_window = []
for ps in E03_P_SWITCH_VALUES:
env = TwoDoorEnv(p_correct=E03_P_CORRECT, p_switch=ps)
np.random.seed(42)
r_m = run_experiment(env, MemorylessAgent(), E03_T, E03_N_EPISODES)
results_e03_memoryless.append(r_m['accuracy'])
np.random.seed(42)
r_b = run_experiment(env, BeliefAgent(E03_P_CORRECT, ps), E03_T, E03_N_EPISODES)
results_e03_belief.append(r_b['accuracy'])
np.random.seed(42)
r_w = run_experiment(env, WindowAgent(E03_K, E03_P_CORRECT, ps), E03_T, E03_N_EPISODES)
results_e03_window.append(r_w['accuracy'])
results_e03_memoryless = np.array(results_e03_memoryless)
results_e03_belief = np.array(results_e03_belief)
results_e03_window = np.array(results_e03_window)
markov_costs_e03 = results_e03_belief - results_e03_memoryless
# Find crossover point (where Markov cost ≈ 0)
crossover_idx = np.argmin(np.abs(markov_costs_e03))
crossover_ps = E03_P_SWITCH_VALUES[crossover_idx]
print(f" {'p_switch':>10} {'Memoryless':>12} {'Belief':>10} {'Δ(cost)':>10}")
for i, ps in enumerate(E03_P_SWITCH_VALUES[::3]):
idx = list(E03_P_SWITCH_VALUES).index(ps) if ps in E03_P_SWITCH_VALUES else i*3
print(f" {ps:>10.3f} {results_e03_memoryless[i*3]:>12.4f} "
f"{results_e03_belief[i*3]:>10.4f} {markov_costs_e03[i*3]:>10.4f}")
print(f"\n Memoryless cost ≈ 0 near p_switch = {crossover_ps:.3f}")
# --- Plot ---
fig, axes = plt.subplots(1, 2, figsize=(11, 4))
fig.suptitle(f"E03 — State Persistence Sweep\np_correct={E03_P_CORRECT}, k={E03_K}", y=1.01)
ax = axes[0]
ax.plot(E03_P_SWITCH_VALUES, results_e03_belief, color=COLORS['belief'],
lw=2, label='BeliefAgent (optimal)')
ax.plot(E03_P_SWITCH_VALUES, results_e03_window, color=COLORS['window_10'],
lw=1.8, ls='--', label=f'WindowAgent(k={E03_K})')
ax.plot(E03_P_SWITCH_VALUES, results_e03_memoryless, color=COLORS['memoryless'],
lw=2, label='MemorylessAgent')
ax.axhline(E03_P_CORRECT, color='black', lw=0.8, ls=':', label=f'p_correct={E03_P_CORRECT}')
ax.set_xlabel("p_switch (state switch probability per step)")
ax.set_ylabel("Mean accuracy")
ax.set_title("Accuracy vs state persistence")
ax.set_xlim(0, 0.5)
ax.legend(fontsize=9)
ax = axes[1]
ax.fill_between(E03_P_SWITCH_VALUES, 0, markov_costs_e03,
color=COLORS['memoryless'], alpha=0.25, label='Memoryless cost (Belief − Memoryless)')
ax.plot(E03_P_SWITCH_VALUES, markov_costs_e03, color=COLORS['memoryless'], lw=2)
ax.plot(E03_P_SWITCH_VALUES, results_e03_belief - results_e03_window,
color=COLORS['window_10'], lw=1.8, ls='--',
label=f'WindowAgent(k={E03_K}) residual cost')
ax.axhline(0, color='black', lw=0.8)
ax.axvline(0.5, color='black', lw=0.8, ls=':', alpha=0.5, label='i.i.d. limit (p_switch=0.5)')
ax.set_xlabel("p_switch")
ax.set_ylabel("Accuracy gap")
ax.set_title("Cost of memoryless inference vs world dynamics")
ax.set_xlim(0, 0.5)
ax.legend(fontsize=9)
plt.tight_layout()
plt.savefig('e03_persistence_sweep.png', bbox_inches='tight')
plt.close()
print("Saved: e03_persistence_sweep.png")
FINDING 3: The cost of memoryless inference decreases monotonically as p_switch increases. At p_switch → 0.5 (i.i.d. observations), MemorylessAgent ≈ BeliefAgent — history is irrelevant because each observation is independent of the last. At p_switch → 0 (persistent state), history carries strong predictive value and the memoryless cost is highest. WindowAgent(k=10) tracks BeliefAgent closely for all p_switch values tested, confirming that a finite window suffices when the world is not too persistent.
E04 — 2D cost map: p_correct × p_switch¶
Hypothesis: The memoryless inference cost depends on two independent factors:
- Channel quality (p_correct): higher quality makes each observation more decisive, so history adds less marginal value — but also makes history MORE reliable as evidence.
- World dynamics (p_switch): more switching means history decays faster.
The interaction between these factors determines the 2D cost landscape.
Setup: Grid over p_correct ∈ [0.55, 0.95] × p_switch ∈ [0.01, 0.45], T=60, n_episodes=1500.
print("\nE04: 2D cost map (p_correct × p_switch)")
print("=" * 50)
E04_P_CORRECT_VALS = np.linspace(0.55, 0.95, 9)
E04_P_SWITCH_VALS = np.linspace(0.01, 0.45, 9)
E04_T = 60
E04_N_EPISODES = 1500
cost_grid = np.zeros((len(E04_P_SWITCH_VALS), len(E04_P_CORRECT_VALS)))
belief_grid= np.zeros_like(cost_grid)
for i, ps in enumerate(E04_P_SWITCH_VALS):
for j, pc in enumerate(E04_P_CORRECT_VALS):
env = TwoDoorEnv(p_correct=pc, p_switch=ps)
np.random.seed(0)
r_m = run_experiment(env, MemorylessAgent(), E04_T, E04_N_EPISODES)
np.random.seed(0)
r_b = run_experiment(env, BeliefAgent(pc, ps), E04_T, E04_N_EPISODES)
cost_grid[i, j] = r_b['accuracy'] - r_m['accuracy']
belief_grid[i, j] = r_b['accuracy']
print(f" Max memoryless cost in grid: {cost_grid.max():.4f} "
f"at p_correct={E04_P_CORRECT_VALS[cost_grid.max(1).argmax() % len(E04_P_CORRECT_VALS)]:.2f}, "
f"p_switch={E04_P_SWITCH_VALS[cost_grid.max(axis=1).argmax()]:.3f}")
print(f" Min memoryless cost in grid: {cost_grid.min():.4f}")
# --- Plot ---
fig, axes = plt.subplots(1, 2, figsize=(12, 5))
fig.suptitle("E04 — 2D Cost of Memoryless Inference", y=1.01)
ax = axes[0]
im = ax.imshow(cost_grid, origin='lower', aspect='auto', cmap='RdYlGn_r',
extent=[E04_P_CORRECT_VALS[0], E04_P_CORRECT_VALS[-1],
E04_P_SWITCH_VALS[0], E04_P_SWITCH_VALS[-1]],
vmin=0, vmax=cost_grid.max())
plt.colorbar(im, ax=ax, label='Accuracy gap (Belief − Memoryless)')
ax.set_xlabel("p_correct (channel quality)")
ax.set_ylabel("p_switch (state switch probability)")
ax.set_title("Memoryless inference cost\n(red = high cost, green = low cost)")
ax = axes[1]
im2 = ax.imshow(belief_grid, origin='lower', aspect='auto', cmap='Blues',
extent=[E04_P_CORRECT_VALS[0], E04_P_CORRECT_VALS[-1],
E04_P_SWITCH_VALS[0], E04_P_SWITCH_VALS[-1]])
plt.colorbar(im2, ax=ax, label='BeliefAgent accuracy')
ax.set_xlabel("p_correct")
ax.set_ylabel("p_switch")
ax.set_title("BeliefAgent accuracy\n(reference: what is achievable)")
plt.tight_layout()
plt.savefig('e04_2d_cost_map.png', bbox_inches='tight')
plt.close()
print("Saved: e04_2d_cost_map.png")
FINDING 4: The 2D cost map reveals a non-trivial interaction. The memoryless inference cost is highest when:
- p_switch is LOW (persistent state → history carries evidence) AND
- p_correct is INTERMEDIATE (channel is informative but not decisive — history helps most when individual observations are uncertain but their aggregate is reliable).
At high p_correct (e.g. 0.95), the MemorylessAgent already achieves near-optimal accuracy (each single observation is almost certainly correct), so history adds little. This is a precision finding: discarding observation history is most costly in the regime where observations are moderately noisy AND the world is persistent — exactly the regime where autonomous systems operate in practice.
E05 — Minimum sufficient memory depth¶
Hypothesis: For each (p_correct, p_switch) pair, there exists a minimum window depth k* such that WindowAgent(k*) achieves accuracy within ε = 0.01 of BeliefAgent. k* should scale approximately as 1/p_switch (the state persistence length).
Setup: p_correct=0.8, p_switch ∈ [0.05, 0.45], k tested ∈ {1,2,3,4,5,7,10,15,20,30}, T=100, n_episodes=2000.
print("\nE05: Minimum sufficient memory depth")
print("=" * 50)
E05_P_SWITCH_VALUES = np.array([0.05, 0.08, 0.10, 0.15, 0.20, 0.25, 0.30, 0.40])
E05_K_VALUES = [1, 2, 3, 4, 5, 7, 10, 15, 20, 30]
E05_P_CORRECT = 0.8
E05_T = 100
E05_N_EPISODES = 2000
E05_EPSILON = 0.01 # tolerance for "near-optimal"
min_k_results = {}
belief_accuracy = {}
print(f" {'p_switch':>10} {'1/p_switch':>12} {'Belief acc':>12} {'Min k*':>8}")
for ps in E05_P_SWITCH_VALUES:
env = TwoDoorEnv(p_correct=E05_P_CORRECT, p_switch=ps)
np.random.seed(42)
r_b = run_experiment(env, BeliefAgent(E05_P_CORRECT, ps), E05_T, E05_N_EPISODES)
target_acc = r_b['accuracy'] - E05_EPSILON
belief_accuracy[ps] = r_b['accuracy']
min_k = None
for k in E05_K_VALUES:
np.random.seed(42)
r_w = run_experiment(env, WindowAgent(k, E05_P_CORRECT, ps), E05_T, E05_N_EPISODES)
if r_w['accuracy'] >= target_acc:
min_k = k
break
min_k_results[ps] = min_k if min_k is not None else E05_K_VALUES[-1]
print(f" {ps:>10.3f} {1/ps:>12.1f} {r_b['accuracy']:>12.4f} {min_k_results[ps]:>8}")
# --- Plot ---
fig, axes = plt.subplots(1, 2, figsize=(11, 4))
fig.suptitle(f"E05 — Minimum Sufficient Memory Depth\n"
f"p_correct={E05_P_CORRECT}, ε={E05_EPSILON}", y=1.01)
ps_vals = E05_P_SWITCH_VALUES
ks = np.array([min_k_results[ps] for ps in ps_vals])
theory = 1.0 / ps_vals # expected state persistence = 1/p_switch
ax = axes[0]
ax.plot(ps_vals, ks, 'o-', color=COLORS['belief'], lw=2, ms=8, label='Empirical min k*')
ax.plot(ps_vals, theory, '--', color='black', lw=1.5, label='1/p_switch (persistence length)')
ax.set_xlabel("p_switch")
ax.set_ylabel("Minimum sufficient window k*")
ax.set_title("k* needed to reach within ε=0.01 of BeliefAgent")
ax.legend(fontsize=9)
ax = axes[1]
ax.plot(theory, ks, 'o', color=COLORS['belief'], ms=9, label='Empirical k*')
for x, y, ps in zip(theory, ks, ps_vals):
ax.annotate(f'p={ps:.2f}', (x, y), textcoords='offset points',
xytext=(5, 3), fontsize=7, color='#374151')
fit = np.polyfit(theory, ks, 1)
x_line = np.linspace(theory.min(), theory.max(), 50)
ax.plot(x_line, np.polyval(fit, x_line), '--', color='black', lw=1.5,
label=f'Linear fit (slope={fit[0]:.2f})')
ax.set_xlabel("State persistence length (1/p_switch)")
ax.set_ylabel("Minimum sufficient k*")
ax.set_title("k* scales linearly with 1/p_switch")
ax.legend(fontsize=9)
plt.tight_layout()
plt.savefig('e05_minimum_memory.png', bbox_inches='tight')
plt.close()
print("\nSaved: e05_minimum_memory.png")
FINDING 5: The minimum sufficient memory depth k* scales approximately linearly with the state persistence length 1/p_switch. For a world where the state switches every 1/p_switch steps on average, an agent needs roughly that many steps of memory to match the full-history Bayesian. This is a direct empirical confirmation of the theoretical expectation: the effective memory horizon for a first-order Markov chain is its mixing time, which is proportional to 1/p_switch.
Implication for system design: An autonomous agent that cannot maintain full history (due to memory constraints) should allocate a buffer of depth ≈ 1/p_switch to avoid the memoryless inference cost. If p_switch is unknown, a conservative k≈20 covers most practically occurring dynamics.
Summary¶
F.Markov — Empirical conclusions:
Acting on oₜ alone (memoryless inference, treating the current observation as the full state) is suboptimal in partially observable environments with persistent hidden states. The cost is consistent and measurable. Note: the BeliefAgent IS a Markov agent — it acts on bₜ, which is a sufficient statistic. What we measure is the cost of DISCARDING observation history, not the cost of the Markov property itself.
| Experiment | Finding |
|---|---|
| E01 | MemorylessAgent stays flat; BeliefAgent improves over ~20 steps |
| E02 | Performance recovers monotonically with k; largest gains at k=1→3 |
| E03 | Memoryless cost → 0 as p_switch → 0.5 (i.i.d. world); highest at p_switch → 0 |
| E04 | Cost is highest at intermediate p_correct and low p_switch |
| E05 | Minimum sufficient k* ≈ 1/p_switch (state persistence length) |
Connection to Area 01 master question: How should an intelligent system act when it cannot know the world completely? → It should maintain a belief state, not just a current observation. But the depth of history required is bounded by the world's temporal structure. A k-step window with k ≈ 1/p_switch recovers near-optimal performance without requiring unlimited memory — a tractable approximation to full belief tracking.
Open question: These results hold for a first-order Markov world. How does the required memory depth grow when the hidden dynamics are themselves higher-order (sₜ depends on sₜ₋₁, sₜ₋₂, …)? This is addressed in M-series experiment M.Depth.
print("\n" + "=" * 60)
print("Notebook F.Markov complete.")
print("Outputs: e01_markov_cost_baseline.png, e02_history_depth_sweep.png,")
print(" e03_persistence_sweep.png, e04_2d_cost_map.png,")
print(" e05_minimum_memory.png")