RL for Hamiltonian Cycle Discovery

State Space

A state consists of three components:

• Current vertex (i, j, k) — the agent's position in the m-ary cube
• Visited set — which of the m³ vertices have already been visited in this episode
• Step count — how many moves the agent has taken so far

The full state space is enormous. The visited-set component alone has 2^m³ possible configurations. For m=3, that is 2²⁷ ≈ 134 million visited-set states, each combined with 27 possible current vertices. This combinatorial explosion is the central difficulty.

Action Space

At every step the agent chooses one of 3 actions:

1. Bump i — set i ← (i + 1) mod m
2. Bump j — set j ← (j + 1) mod m
3. Bump k — set k ← (k + 1) mod m

The action space is fixed at {0, 1, 2} regardless of m. This is unusually small — the difficulty comes entirely from the state space, not the action space.

Reward Function

The reward is sparse: the large +100 bonus only arrives if the agent perfectly sequences all m³ steps without revisiting any vertex. For m=3 the agent must make 27 correct decisions in a row; for m=5, it must make 125.

1. PPO dominates REINFORCE

Both use the same MLP architecture (32 → 128 → 128 → 3), but PPO's clipped objective and entropy bonus completely prevent the mode collapse that killed REINFORCE. PPO reached 97.25% success rate vs. REINFORCE's 1.16%.

2. GNN-PPO achieves the highest success rate (99.42%)

The graph neural network policy (2-layer message-passing GNN with 64-dim messages) exploits the regular structure of the m-ary cube. It converged to near-perfect performance within ~100 episodes — the fastest among all learned policies. Only 29 failures in 5,000 episodes.

3. MCTS finds cycles without learning

Pure tree search (200 simulations/move, UCB1 selection) achieves 26.5% per-episode success with no training at all. It is expensive per episode but has zero training instability. Useful as a non-learned baseline.

4. REINFORCE suffers catastrophic mode collapse

REINFORCE found 116 cycles in episodes 1–1,100, then converged to a deterministic 24-step suboptimal path and never found another cycle for the remaining 8,900 episodes. This is the classic high-variance policy gradient failure mode: without entropy regularization, the policy becomes too confident too early.

REINFORCE

• Architecture: MLP(32, 128, 128, 3) with ReLU
• Hyperparams: lr=0.003, gamma=0.99, Adam optimizer
• Update: Per-episode, normalized returns
• Weakness: No entropy regularization → premature convergence

PPO (Proximal Policy Optimization)

• Architecture: Actor-Critic MLP, shared backbone (32, 128, 128) + actor head (3) + critic head (1)
• Hyperparams: lr=0.003, gamma=0.99, clip_eps=0.2, entropy_coef=0.01, value_coef=0.5
• PPO epochs: 4 per episode, gradient clipping max_norm=0.5
• Key advantage: Entropy bonus prevents collapse; clipped ratio prevents destructive updates

GNN-PPO (Graph Neural Network + PPO)

• Architecture: 2-layer message-passing GNN (node_feat_dim=4, msg_dim=64) + actor/critic heads
• Node features: (is_current, is_visited, is_start, fiber_s) per vertex
• Message passing: Vectorized with edge index tensors, residual connections, mean aggregation
• PPO settings: Same as MLP-PPO (clip_eps=0.2, entropy=0.01, 4 epochs)
• Key advantage: Exploits graph topology; structurally aware of the m-ary cube

MCTS (Monte Carlo Tree Search)

• Simulations per move: 200
• Selection: UCB1 with c_puct=1.41
• Rollout: Random valid actions until dead end or cycle completion
• Backprop: Normalized path length (1.0 for complete cycle)
• Trade-off: No learning, expensive per episode, but no training instability

1. PPO scales beautifully

PPO achieved 99.48% success rate on 125 vertices — nearly identical to its 97.25% on m=3. First Hamiltonian cycle found around episode 100, near-perfect convergence by episode 200. The simple MLP actor-critic with action masking handles the 4.6× longer episode without difficulty.

2. REINFORCE shows a dramatic phase transition

REINFORCE exhibited a striking three-phase training profile on m=5:

• Episodes 1–400: Rapid climb to 110–124 steps, first successes appear
• Episodes 400–11,800: Long plateau stuck at 124/125 steps, only 110 total successes. Classic mode collapse.
• Episode ~11,800: Sudden breakthrough — the policy snaps to 100% success and never looks back
• Episodes 11,800–20,000: Perfect 100% success rate (8,256 consecutive successes)

This "sudden phase transition" is a remarkable example of how REINFORCE can spend thousands of episodes in a near-optimal but incorrect mode, then catastrophically shift to the correct policy. The overall 41.83% rate is misleading — it was effectively 0.6% for 11,700 episodes, then 100%.

3. GNN-PPO and MCTS hit scaling walls

GNN-PPO could not complete a single episode — the per-node message-passing loop with 125 nodes and 750 edges (bidirectional) takes >8 minutes per episode in Python. A sparse/batched implementation (e.g., PyTorch Geometric) would be needed. MCTS was not attempted: random rollouts on 125 vertices have near-zero probability of finding a Hamiltonian cycle without a learned value function.

1. PPO continues to scale effortlessly

PPO achieved 99.11% success rate on 343 vertices — comparable to m=3 (97.25%) and m=5 (99.48%). First cycle found at ~ep 250, near-perfect by ep 300. The simple 2-layer MLP with action masking handles the 348-dimensional observation and 343-step episodes without any architectural changes. This is now three data points confirming PPO's ~99% success rate is essentially independent of m.

2. REINFORCE phase transition takes even longer

REINFORCE's characteristic three-phase pattern continued at m=7 with an even longer plateau:

• Episodes 1–2,700: Climb to ~300/343 steps, first successes
• Episodes 2,700–26,400: Massive 23,700-episode plateau, stuck near 300–340 steps
• Episode ~26,400: Sudden phase transition to 100% success
• Episodes 26,400–30,000: Perfect 100% (3,600 consecutive successes)

3. REINFORCE phase transition scales predictably

The phase transition pattern is now consistent across three scales:

The plateau roughly doubles from m=5 to m=7 (while vertices increase 2.7×), suggesting REINFORCE can solve arbitrarily large instances given enough episodes — but its training budget grows rapidly and unpredictably. Interestingly, m=3 never recovered at all, possibly because the 10,000-episode budget was insufficient.

1. PPO from scratch still achieves ~99% at 729 vertices

PPO's success rate (99.01%) is consistent with m=3 (97.25%), m=5 (99.48%), and m=7 (99.11%). This is now four data points confirming that PPO's performance is essentially independent of m. First solve around episode 215 — actually faster than m=7 (~ep 250).

2. Zeropad m=3 → m=9 achieves perfect 100% again

Pretraining on tiny m=3 (27 vertices) with zero-padded observations and transferring to m=9 (729 vertices) — a 27× increase in problem size — produces a flawless 30,000/30,000 success rate from episode 1. This replicates the perfect result seen at m=7, confirming the pattern is robust.

3. m=3 is a better pretraining source than m=5

Both zeropad and partial transfer from m=3 outperform their m=5 counterparts at m=9. Zeropad m=3 achieves 100.00% vs. m=5's 99.91%; partial m=3 achieves 99.99% vs. m=5's 99.13%. This may be because m=3 pretraining converges faster (smaller environment) and the learned strategy is equally general — further evidence that the navigation skill is completely scale-invariant.

1. PPO from scratch shows first signs of degradation

PPO's from-scratch success rate drops to 97.79% — still high, but noticeably below the ~99% plateau seen at m=5/7/9. First solve moves to ~ep 350, up from ~215 at m=9. The 1,331-step episode is starting to stress credit assignment and the 128-unit hidden layer is compressing a 1,336-dim input. This is the first scale where from-scratch PPO shows wear.

2. Zeropad transfer achieves perfect 100% from both m=3 and m=5

Both zeropad sources achieve flawless 30,000/30,000 at m=11 — a 49× scale-up from m=3 (27 → 1,331 vertices). This is the first scale where m=5 zeropad matches m=3, both achieving perfect results. Transfer learning completely compensates for the from-scratch degradation.

3. The baseline-to-transfer gap is widening

As from-scratch PPO's success rate slowly declines with scale (97.79% at m=11 vs 99.48% at m=5), transfer learning's advantage grows from marginal to meaningful. At m=11, transfer provides both faster convergence (ep 1 vs ep 350) and higher final performance (100% vs 97.79%). Transfer is no longer just a convenience — it is becoming essential.

1. Transfer eliminates the warmup period entirely

The baseline PPO needs ~215–250 episodes to find its first Hamiltonian cycle on m=7/m=9. All transfer methods solve from episode 1 of finetuning — confirmed on both m=7 (343 vertices) and m=9 (729 vertices). The "navigation strategy" learned on m=3 (27 vertices) transfers across a 27× increase in problem size.

2. Zero-padded m=3 → m=7 achieves perfect 100%

Pretraining on tiny m=3 with zero-padded observations, then finetuning on m=7 or m=9, produces a perfect 30,000/30,000 success rate in both cases. This is better than from-scratch PPO (~99%) and every other transfer variant. The zero-padding preserves the input projection's understanding of visited-mask patterns, giving it a head start.

3. Even partial transfer works immediately

Partial transfer only preserves hidden layers — the input projection is randomly reinitialized for the new 348-dim input. Despite this, it solves m=7 from episode 1 at 99.99%. This means the hidden layers encode a generalizable navigation policy largely independent of the input encoding.

4. Source problem size barely matters

Both m=3 and m=5 pretrained models transfer equally well. The 27-vertex problem teaches essentially the same strategy as the 125-vertex problem. The core skill — "how to use the action mask and visited information to navigate a 3-cube digraph" — is scale-invariant.

1. Observation dimension: O(m³)

The visited mask is an m³-bit vector, so the network input grows cubically. For m=3 the observation is 32-dimensional; for m=5 it is 130; for m=7 it is 348; for m=9 it is 734; for m=11 it is 1,336. PPO handles all of these without architectural changes, though from-scratch performance shows first signs of stress at 1,336 dimensions.

2. Episode length: O(m³)

A successful episode requires exactly m³ steps. Longer episodes mean: (a) more forward passes per episode, increasing wall-clock time linearly; (b) longer credit-assignment horizons, making it harder for the agent to attribute the final +100 reward to early actions; (c) more opportunities for a single wrong decision to terminate the episode.

Empirical growth: PPO episodes-to-first-solve: 50 (m=3) → 100 (m=5) → 250 (m=7) → 215 (m=9) → 350 (m=11). The growth is sub-linear relative to vertex count, but m=11 shows the first uptick. Transfer learning eliminates warmup entirely (ep 1 for all tested scales m=7 through m=11).

3. Theoretical state space: O(2^m³)

The visited-set tracking creates an exponentially growing state space. However, results across m=3, 5, 7, 9, and 11 consistently show that this theoretical explosion does not translate to practical difficulty for function-approximation RL. PPO maintains 97–99% success rate as the state space grows from 10⁸ to 10⁴⁰⁰. The MLP never enumerates states — it learns to generalize. The real bottleneck is episode length and credit assignment, not raw state-space size.

Estimated Practical Limit: m ≈ 13–15 (with transfer)

With five confirmed scales (m=3,5,7,9,11) and perfect transfer learning through m=11, the estimated limit continues to rise. However, m=11 is the first scale showing from-scratch degradation (97.79%), suggesting we are approaching a capacity limit.

• m=13 (2,197 vertices): Likely feasible with transfer. Zeropad transfer has achieved perfect 100% at every tested scale (m=7 through m=11). The from-scratch rate may drop further below 97%, but transfer should compensate. The observation (2,202-dim) is 17× larger than the 128-unit hidden layer — a compression ratio that PPO has handled so far but may strain.
• m=15 (3,375 vertices): At the frontier. The 3,375-step episode is long and the 3,380-dim observation may exceed the 128-unit MLP's capacity to compress. Wider hidden layers (256 or 512 units) might be needed. Transfer from m=3 may still achieve near-perfect results.
• m ≥ 17 (4,913+ vertices): Standard 2-layer MLP is likely insufficient without architectural scaling (wider/deeper networks, attention, or hierarchical decomposition). Episodes exceed 4,900 steps and the visited mask dominates the observation.

The key lesson from m=3 through m=11: the exponential state space is a red herring. What actually limits RL is network capacity relative to the observation dimension and episode length for credit assignment. PPO from scratch maintains 97–99% success as the state space grows from 10⁸ to 10⁴⁰⁰. Transfer learning from m=3 provides perfect 100% results at every tested scale up to m=11 (49× scale increase). The practical limit with transfer is likely where the 128-unit hidden layer can no longer compress the policy — around m=13–15.

1. Inventing the fiber concept

Recognizing s = (i+j+k) mod m as the organizing principle was an act of mathematical creativity — defining a new variable that simplifies the problem. RL has no mechanism for inventing new state representations. The agent sees vertices and bumps; it cannot decide "I should group these vertices by the sum of their coordinates modulo m."

2. The direction string abstraction

Compressing the assignment of 3m³ arcs to 3 cycles into 6 conditional rules using permutations of "012" requires understanding symmetry. The insight that each vertex's three outgoing arcs should be assigned to the three cycles via a permutation — and that the permutation depends only on fiber index and one coordinate — is a representational leap that no reward signal can guide toward.

3. The universality argument

The rules work for all odd m because the conditions (s=0, s=m−1, i=m−1, j=m−1) are defined relative to m, not using absolute values. Moving from "this works for m=3, 5, 7" to "this works for all odd m" requires logical deduction about parameterized families — a form of reasoning RL does not perform.

4. Using computation as a tool, not an end

In explorations 16–24, Claude used simulated annealing to find solutions for small m, then looked at the solutions to extract patterns. This is meta-reasoning — using computation to generate data, then reasoning about that data. RL just runs the computation; it doesn't step back and ask "what do these solutions have in common?"

Approach 1: Program Synthesis RL

Train an agent to write a program (like Knuth's C code) that generates valid Hamiltonian cycles for arbitrary m. The action space would be token-level code generation; the reward would be running the program for m=3, 5, 7, … and checking validity.

Problem: The search space over program tokens is astronomically larger than finding a cycle for one m. The agent would need to discover fiber structure, direction strings, and conditional rules through trial and error over code tokens — without any guidance toward the right abstractions.

Approach 2: Conjecture-and-Verify RL

Let the agent propose parametric rules (e.g., "if s=0 and j=m−1, use direction '012'") and verify them computationally for increasing m values. Reward: +1 for each m where the rules produce valid decompositions.

This is closest to what Claude actually did in explorations 16–24. But the critical step was the abstraction: recognizing that the pattern depends on fiber index and one coordinate. An RL agent over rule templates would need this abstraction space pre-defined — which begs the question of who supplies the insight.

Approach 3: Multi-Level Abstraction Learning (Most Ambitious)

A multi-level system where:

• Level 1: Find cycles for specific m (what we've done with RL)
• Level 2: Compare trained policies across m values, extract shared structure
• Level 3: Propose parametric rules that explain the shared structure

This mirrors Claude's actual path. But the Level 2 → 3 transition requires symbolic abstraction — going from "here are 5 trained neural network policies" to "the decision depends on (i+j+k) mod m and whether i=m−1." This is an open problem in AI.