Dipping my toes into Reinforcement Learning (RL) by playing with the Traveling Salesman Problem (TSP).

Motivation

I recently competed in the kaggle competition Kaggriculture. It was a lot of fun, but sadly I didn’t do as well as I would have liked. I placed around 135/11337. (I was shooting for top 10).

I (incorrectly) thought that due to the competition having market functions (the prices of crops fluctuated), that a rules based heuristics bot would do better than a reinforcement learning (RL) bot. It seems reasonable that I could correctly estimate the ideal crop schedules, and that it would be hard for RL to precisely estimate (and every dollar matters). I was top 10 for a bit, but the imitation and RL bots eventually caught up and beat me. It’s also slightly frustrating to think about how much more effort I put into the competition compared to the RL bots. (I assume). It was many 16 hour days (I try not to use LLMs too much either).

This was the final straw for me to finally just learn RL. People are writing better solutions for less effort. If you can’t beat ’em, join em. It also seems like a very valuable skill.

(I still think that in theory a rules based bot should be able to do better, it’s just harder, and I need more time (I started late, and was sick with the flu for 1.5 weeks). But maybe I’m antiquated and living in the past. Hopefully these experiments will help me see the light)

Anyways, to see how much better RL can do, I did a bit of the Hugging Face RL course and now I’m starting to play with Traveling Salesman Problem (TSP) and Vehicle Routing Problems (VRP) to see how much better/fast RL is at finding good solutions. Eventually I’ll mold the problem closer to the kaggriculture problem, but for now, baby steps.

Setup

I’m using Gymnasium to model the TSP game. It’s a simple grid, and some squares have a “task count”. Right now the for the TSP it’s just set to 1. For the VRP I’ll be set to something higher. The goal is to finish as many tasks as possible in 24 hours.

I’m currently doing a pretty naive observation, just giving the model the raw grid, agent position, and hour (out of 24).

self.observation_space = cast(gym.Space[Observation], gym.spaces.Dict({
  "agent": gym.spaces.Box(0, size-1, shape=(2,), dtype=np.int8),
  "grid": gym.spaces.Box(0, 24, (size*size,), dtype=np.int8),
  "hour": gym.spaces.Discrete(25),
}))

The model is trained using StableBaselines3 PPO. Why PPO? No intelligent reason, it’s just the one I was using for some of the HuggingFace assignments, and I recognize it. The interface is also incredibly simple.

Results

I trained on 10_000_000 timesteps (takes about 30 minutes), and got the following results:

For a 5x5 Grid:

[+] Average scores over 100 games: PPO=9.26, Held Karp=9.90, Greedy + 2-opt=9.44

For a 6x6 Grid:

[+] Average scores over 100 games: PPO=9.42, Held Karp=10.70, Greedy + 2-opt=9.86

It’s pretty interesting that the Greedy + 2Opt algorithm is better than the PPO, and obviously both are worse than the exact solution (Held Karp). But Held Karp doesn’t work on 7x7 or bigger. Karp is \( O(n^2 2^n) \).

In the Kaggriculture competition I was using a Greedy + 2-opt solution, so at least so far, a naive RL model does not seem to beat my existing solution.

Next Steps

Now that we have everything setup, I’m going to see how I can improve the observation space to maybe get better results, potentially swap PPO for something more appropriate, and also see how it scales with grid size. Then after I feel good with the TSP problem, I’ll convert to a VRP.