publishing my previous post on benchmarking tabular reinforcement studying (RL) strategies, I couldn’t shake the sensation that one thing wasn’t fairly proper. The outcomes seemed off, and I wasn’t absolutely glad with how they turned out.
Nonetheless, I continued with the publish collection, shifting focus to multi-player video games and approximate resolution strategies. To help this, I’ve been steadily refactoring the unique framework we constructed. The brand new model is cleaner, extra basic, and simpler to make use of. Within the course of, it additionally helped uncover a number of bugs and edge-case points in among the earlier algorithms (extra on that later).
On this publish, I’ll introduce the up to date framework, spotlight the errors I made, share corrected outcomes, and mirror on key classes discovered, setting the stage for extra advanced experiments to return.
The up to date code will be discovered on GitHub.
Framework
The largest change from the earlier model of the code is that RL resolution strategies at the moment are carried out as lessons. These lessons expose frequent strategies like act() (for choosing actions) and replace() (for adjusting mannequin parameters).
Complementing this, a unified coaching script manages the interplay with the atmosphere: it generates episodes and feeds them into the suitable methodology for studying—utilizing the shared interface offered by these class strategies.
This refactoring considerably simplifies and standardizes the coaching course of. Beforehand, every methodology had its personal standalone coaching logic. Now, coaching is centralized, and every methodology’s position is clearly outlined and modular.
Earlier than diving into the tactic lessons intimately, let’s first take a look at the coaching loop for single-player environments:
def train_single_player(
env: ParametrizedEnv,
methodology: RLMethod,
max_steps: int = 100,
callback: Callable | None = None,
) -> tuple[bool, int]:
"""Trains a technique on single-player environments.
Args:
env: env to make use of
methodology: methodology to make use of
max_steps: maximal variety of replace steps
callback: callback to find out if methodology already solves the given downside
Returns:
tuple of success, discovered coverage, variety of replace steps
"""
for step in vary(max_steps):
remark, _ = env.env.reset()
terminated = truncated = False
episode = []
cur_episode_len = 0
whereas not terminated and never truncated:
motion = methodology.act(remark, step)
observation_new, reward, terminated, truncated, _ = env.step(
motion, remark
)
episode.append(ReplayItem(remark, motion, reward))
methodology.replace(episode, step)
remark = observation_new
# NOTE: that is extremely depending on atmosphere dimension
cur_episode_len += 1
if cur_episode_len > env.get_max_num_steps():
break
episode.append(ReplayItem(observation_new, -1, reward, []))
methodology.finalize(episode, step)
if callback and callback(methodology, step):
return True, step
env.env.shut()
return False, stepLet’s visualize what a accomplished episode appears to be like like—and when the replace() and finalize() strategies are known as through the course of:
After every replay merchandise is processed—consisting of a state, the motion taken, and the reward acquired—the tactic’s replace() operate is named to regulate the mannequin’s inner parameters. The particular conduct of this operate is dependent upon the algorithm getting used.
To offer you a concrete instance, let’s take a fast take a look at how this works for Q-learning.
Recall the Q-learning replace rule:
When the second name to replace() happens, we have now St = s1, At = a1 and Rt+1 = r2.
Utilizing this info, the Q-learning agent updates its worth estimates accordingly.
Unsupported Strategies
Dynamic programming (DP) strategies don’t match above launched construction – since they’re based mostly upon iterating over all states of the atmosphere. For that purpose, we depart their code untouched and deal with coaching them in a different way.
Additional, we utterly take away the help for Prioritized Sweeping. Additionally, right here we have to iterate over states not directly to seek out predecessor states, which, once more – doesn’t match into our replace coaching construction – and, extra importantly, will not be possible for extra advanced multi-player video games, the place the variety of states is far bigger and tougher to iterate.
Since this methodology in any case didn’t produce good outcomes, we concentrate on the remaining ones. Observe: the same reasoning was carried out for DP strategies: these can’t be prolonged so simply to multi-player video games, and thus can be of lesser curiosity sooner or later.
Bugs
Bugs occur — all over the place, and this challenge is not any exception. On this part, I’ll spotlight a very impactful bug that made its means into the outcomes of the earlier publish, together with some minor modifications and enhancements. I’ll additionally clarify how these affected earlier outcomes.
Incorrect Motion Likelihood Calculation
Some strategies require the chance of a selected motion through the replace step. Within the earlier code model, we had:
def _get_action_prob(Q: np.ndarray) -> float:
return (
Q[observation_new, a] / sum(Q[observation_new, :])
if sum(Q[observation_new, :])
else 1
)This labored just for strictly optimistic Q-values, however broke down when Q-values had been unfavorable — making the normalization invalid.
The corrected model handles each optimistic and unfavorable Q-values correctly utilizing a softmax strategy:
def _get_action_prob(self, remark: int, motion: int) -> float:
probs = [self.Q[observation, a] for a in vary(self.env.get_action_space_len())]
probs = np.exp(probs - np.max(probs))
return probs[action] / sum(probs)This bug considerably impacted Anticipated SARSA and n-step Tree Backup, as their updates relied closely on motion chances.
Tie-Breaking in Grasping Motion Choice
Beforehand, when producing episodes, we both chosen the grasping motion or sampled randomly with ε-greedy logic:
def get_eps_greedy_action(q_values: np.ndarray, eps: float = 0.05) -> int:
if random.uniform(0, 1) < eps or np.all(q_values == q_values[0]):
return int(np.random.alternative([a for a in range(len(q_values))]))
else:
return int(np.argmax(q_values))Nonetheless, this didn’t correctly deal with ties, i.e., when a number of actions shared the identical most Q-value. The up to date act() methodology now consists of truthful tie-breaking:
def act(
self, state: int, step: int | None = None, masks: np.ndarray | None = None
) -> int:
allowed_actions = self.get_allowed_actions(masks)
if self._train and step and random.uniform(0, 1) < self.env.eps(step):
return random.alternative(allowed_actions)
else:
q_values = [self.Q[state, a] for a in allowed_actions]
max_q = max(q_values)
max_actions = [a for a, q in zip(allowed_actions, q_values) if q == max_q]
return random.alternative(max_actions)A small change, however probably fairly related – since this e.g. stimulates a extra explorative motion choice in the beginning of every coaching, the place all Q-values are equal.
This small change could have a noticeable impression—particularly early in coaching, when all Q-values are initialized equally. It encourages a extra various exploration technique through the crucial early part.
As beforehand mentioned—and as we’ll see once more beneath—RL strategies exhibit excessive variance, making the impression of such modifications troublesome to measure exactly. Nonetheless, this adjustment appeared to barely enhance the efficiency of a number of strategies: Sarsa, Q-learning, Double Q-learning, and Sarsa-n.
Up to date Outcomes
Let’s now look at the up to date outcomes — for completeness, we embrace all strategies, not simply the improved ones.
However first, a fast reminder of the duty we’re fixing: we’re working with Gymnasium’s GridWorld atmosphere [2] — primarily a maze-solving job:
The agent should navigate from the top-left to the bottom-right of the grid whereas avoiding icy lakes.
To guage every methodology’s efficiency, we scale the gridworld dimension and measure the variety of replace steps till convergence.
Monte Carlo Strategies
These strategies weren’t affected by the latest implementation modifications, so we observe outcomes per our earlier findings:
- Each are able to fixing environments as much as 25×25 in dimension.
- On-policy MC performs barely higher than off-policy.
Temporal Distinction Strategies
For these, we measure the next outcomes:
For these, we instantly discover that Anticipated Sarsa now fares a lot better, because of fixing above talked about bug about computing the motion chances.
But in addition the opposite strategies carry out higher: as talked about above, this might simply be likelihood / variance – or be a consequence of the opposite minor enhancements we did, specifically the higher dealing with of ties throughout motion choice.
TD-n
For TD-n strategies, our outcomes look a lot totally different:
Sarsa-n additionally has improved, in all probability for comparable causes as mentioned within the final part – however specifically n-step tree backup now performs very well – proving that with appropriate motion choice this certainly is a really highly effective resolution methodology.
Planning
For planning, we solely have Dyna-Q left – which additionally appears to have improved barely:
Evaluating the Greatest Answer Strategies on Bigger Environments
With that, let’s visualize the best-performing strategies from all classes in a single diagram. As a result of removing of some strategies like DP, I now chosen on-policy MC, Sarsa, Q-learning, Sarsa-n, n-step tree backup and Dyna-Q.
We start by displaying outcomes for grid worlds as much as dimension 50 x 50:
We observe on-policy MC to carry out surprisingly nicely — per earlier findings. Its energy probably stems from its simplicity and unbiased estimates, which work nicely for short- to medium-length episodes.
Nonetheless, not like the earlier publish, n-step Tree Backup clearly emerges because the top-performing methodology. This aligns with principle: its use of anticipated multi-step backups permits easy and steady worth propagation, combining the strengths of off-policy updates with the steadiness of on-policy studying.
Subsequent, we observe a center cluster: Sarsa, Q-learning, and Dyna-Q — with Sarsa barely outperforming the others.
It’s considerably stunning that the model-based updates in Dyna-Q don’t result in higher efficiency. This would possibly level to limitations within the mannequin accuracy or the variety of planning steps used. Q-learning tends to underperform because of the elevated variance launched by its off-policy nature.
The worst-performing methodology on this experiment is Sarsa-n, per earlier observations. We suspect the degradation in efficiency comes from the elevated variance and bias because of n-step sampling with out expectation over actions.
It’s nonetheless considerably surprising that MC strategies outperform TD on this setting — historically, TD strategies are anticipated to do higher in giant environments. Nonetheless, that is mitigated in our setup by the reward shaping technique: we offer a small optimistic reward at every step because the agent strikes nearer to the objective. This alleviates one in every of MC’s main weaknesses — poor efficiency in sparse reward settings.
Conclusion and Learnings
On this publish, we shared updates to the RL framework developed over this collection. Alongside numerous enhancements, we fastened some bugs — which considerably enhanced algorithm efficiency.
We then utilized the up to date strategies to more and more bigger GridWorld environments, with the next findings:
- n-step Tree Backup emerged as the perfect methodology general, because of its anticipated multi-step updates that mix the advantages of each on- and off-policy studying.
- Monte Carlo strategies adopted, displaying surprisingly robust efficiency because of their unbiased estimates and the intermediate rewards guiding studying.
- A cluster of TD strategies — Q-learning, Sarsa, and Dyna-Q — adopted. Regardless of Dyna-Q’s model-based updates, it didn’t considerably outperform its model-free counterparts.
- Sarsa-n carried out worst, probably because of the compounded bias and variance launched by sampling n-step returns.
Thanks for studying this replace! Keep tuned for additional content material — subsequent up, we cowl multi-player video games and environments.
