Colosseum Eval

---
name: colosseum-eval
description: 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). Use when the user wants to benchmark on Colosseum, or asks about evaluating this task. Reports per-step normalized cumulative regret.
metadata:
  skill_kind: dataset_eval
  source_arxiv: 2210.13075
  bibtex_key: conserva2022hardness
  confidence: high
---

# 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

```python
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

```bibtex
@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