Discussion on Apr. 1

[isPANN]

TODOs:

• Learn Reinforcement Learning Foundations
• Search Crossing Gadget for QUBOModel on Triangular lattice
• The verification code for a candidate should be transfered to Rust (I'll make a plan first), add Python bindings.

[isPANN]

@Ferrari-72 For task 1, you can follow this plan. Learn by this hands-on project.

Goal

Train an RL agent to construct small weighted graphs satisfying a target truth table constraint — a simplified version of gadget search.

Problem Setup

4-node complete graph, QUBO model, target = AND gate truth table. Verification is brute-force over all 2^4 = 16 states. A solution is guaranteed to exist (the Julia ILP solver already finds one).

Prerequisites

• Understand Markov Decision Process (states, actions, rewards, transitions) and policy gradient (REINFORCE)
• Setup Python environment: uv pip install gymnasium torch torch-geometric
• Rewrite the energy function from src/core/search.jl:516-525 in Python as your simple verifier

Milestones

1. Environment: Build a Gymnasium env for graph weight assignment. Validate it by plugging in the known ILP solution.
2. REINFORCE: Implement basic policy gradient. Get a reward curve that trends upward.
3. PPO: Upgrade to PPO (use CleanRL as reference). Compare stability with REINFORCE.
4. Reward shaping: Experiment with sparse / proportional / energy-gap rewards. See which helps most.
5. MCTS: Implement tree search as a non-gradient alternative. Compare sample efficiency with PPO.
6. GNN encoder: Replace MLP with a GIN state encoder in PPO. Compare. (May show no advantage at 4 nodes — valid finding; try 6-8 nodes if so.)
7. Report: Test all methods on AND/OR/XOR, summarize what worked and what didn't.