Colosseum Eval

colosseum-eval

Hardness in Markov Decision Processes: Theory and Practice — Conserva et al. (2022) (arXiv:2210.13075, 2022)

What this evaluates

Evaluates reinforcement learning agents on tabular Markov Decision Processes (MDPs) to measure their performance under varying theoretical hardness criteria, specifically state-action coverage (diameter) and reward structure (environmental value norm).

Datasets

• Colosseum — total ?; splits: test (-1)

Metrics

• per-step normalized cumulative regret (primary) — range: [0, 1]
  • Calculated as the difference between the optimal cumulative reward and the agent's actual cumulative reward, divided by the total number of time steps (horizon). It provides a unified scale across different MDPs, where 0 represents optimal performance and 1 represents worst-case performance.

Input / output format

Input: State observations from a tabular Markov Decision Process (MDP) environment.

Output: Action selection policy or Q-value updates over a sequence of time steps.

Scoring recipe

def compute_normalized_cumulative_regret(agent_rewards, optimal_reward, horizon):
    cumulative_regret = optimal_reward - sum(agent_rewards)
    return cumulative_regret / horizon

Common pitfalls

• Agents are subject to a strict time limit (10 minutes for tabular) and may be interrupted before reaching the 500,000 time step cap, requiring the use of the last best policy.
• Hyperparameter tuning is performed via random search to minimize regret across a diverse subset of environments (12 MDPs per family), not directly on the final test set.
• The benchmark separates episodic and continuous settings, which drastically changes how regret accumulates and when algorithms like PSRL or UCRL2 terminate early.

Evidence (verbatim from paper)

The per-step normalized cumulative regret (defined in App. C) is employed as a performance measure since it provides a unified scale across different MDPs. Each interaction between an agent and an MDP is repeated for 20 seeds. The performance indicators are computed every 100 time steps.

Citation

@misc{conserva2022hardness,
  title={Hardness in Markov Decision Processes: Theory and Practice},
  author={Conserva et al. (2022)},
  year={2022},
  note={arXiv:2210.13075}
}

• arXiv: 2210.13075