SYNTOLOGY HomeExplorerAtlasCodeMethodologyAboutDevelopersFeedPricing
Paper · 2602.05591 · 2026

Efficient Algorithms for Robust Markov Decision Processes with s-Rectangular Ambiguity Sets

Marek Petrik, Wolfram Wiesemann, Chin Ho

arXiv · PDF

Code that ran

7 of 7 samples (functions and classes) lifted from this paper's linked repositories executed on a synthesized input in Syntology's jail (0 of them constructed an object rather than computing a result; 2 honoured the contract we drafted, 0 violated it and 0 have no contract verdict; 5 failures of our instrument; 0 no recorded run), measured 2026-11-22; bodies inline only under a permissive licence as GitHub detects it. Not a reproduction of the paper's results.

"Ran" means the function executed on a synthesized input and returned a value. It is not a reproduction of the paper's results. This record, dated, as JSON: /api/ran/2602.05591.json · badge: /api/ran/2602.05591.svg

Each repository's role is a label: a classifier's output recorded on the link, or, where no role is recorded, what the Papers with Code archive marked. The line under it names its basis. Neither says who wrote the code.

RepositoryRoleRan
google-deepmind/open_spiel canonical (classifier label)
classifier basis: census
7 ran · 0 no recorded run
FunctionStatusWhere it lives
array_to_strat_dict Ran
ran; our contract draft was wrong, not the code
google-deepmind/open_spiel/open_spiel/python/algorithms/efr.py
code served (permissive licence) · get_code("a3fae536b901b362")
How it ran

Ran in Syntology's sandbox on this synthesized input (drafted by a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API) and returned dict. The image it ran in was not recorded. If your copy returns the same type on these inputs, it matched what we observed; nothing here checks that. It does NOT mean the output is correct: nothing has compared it to the paper.

import torch
import numpy as np

torch.manual_seed(0)

# The function takes a strategy_array and legal_actions
# strategy_array should be array-like with values corresponding to each legal action
# legal_actions should be a list of actions

# Create a small strategy array (probabilities for each action)
strategy_array = np.array([0.2, 0.5, 0.3])

# Create a list of legal actions
legal_actions = ["action_0", "action_1", "action_2"]

ARGS = {
    "strategy_array": strategy_array,
    "legal_actions": legal_actions,
}
Setup block drafted by
a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API
Imports
numpy, torch — import names as written, not package names to install; a name the repository itself provides is not a package
Returned
type dict — a dict output has no array shape of its own; none is stated — the instrument coerces any output to an array; for a dict output the recorded ndim 0 and dtype family float describe that coercion, not the output, and are not stated
Environment
image not recorded; re-verify against syntology-harvest-sandbox:v5-deps; not recorded for this sample: the harness installs a cuda-to-cpu shim (cuda_shim.py) before every sample and no run records whether a sample needed it; seed: none by the harness; any seed is in the setup block
create_probs_from_index Ran
ran; our contract draft was wrong, not the code
google-deepmind/open_spiel/open_spiel/python/algorithms/efr.py
code served (permissive licence) · get_code("654653a9b1cf7d1b")
How it ran

Ran in Syntology's sandbox on this synthesized input (drafted by a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API) and returned list, ndim 1, dtype family float; no output shape is stated. The image it ran in was not recorded. If your copy returns the same type and ndim on these inputs, it matched what we observed; nothing here checks that. It does NOT mean the output is correct: nothing has compared it to the paper.

import torch
import numpy as np

torch.manual_seed(0)

class MockPolicy:
    def __init__(self):
        # action_probability_array needs to be indexable
        # The function accesses current_policy.action_probability_array[index[1]]
        # where index[1] is an integer, and expects it to return something
        # that can be passed to array_to_strat_dict as strategy_array
        self.action_probability_array = [
            np.array([0.2, 0.3, 0.5]),
            np.array([0.1, 0.4, 0.5]),
            np.array([0.6, 0.2, 0.2]),
            np.array([0.25, 0.25, 0.25, 0.25])
        ]

# indices is a list of tuples where:
# - index[0] is legal_actions (passed to array_to_strat_dict)
# - index[1] is an index into current_policy.action_probability_array
indices = [
    (["action_A", "action_B", "action_C"], 0),
    (["action_X", "action_Y", "action_Z"], 1),
    (["move_1", "move_2", "move_3", "move_4"], 3)
]

current_policy = MockPolicy()

ARGS = {
    "indices": indices,
    "current_policy": current_policy
}
Setup block drafted by
a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API
Imports
numpy, torch — import names as written, not package names to install; a name the repository itself provides is not a package
Returned
type list, ndim 1, dtype family float — a list output has no array shape of its own; none is stated
dtype family
int means an integer dtype; float means any other dtype the instrument saw, bool and complex included (fixture_check.py records only these two families)
Environment
image not recorded; re-verify against syntology-harvest-sandbox:v5-deps; not recorded for this sample: the harness installs a cuda-to-cpu shim (cuda_shim.py) before every sample and no run records whether a sample needed it; seed: none by the harness; any seed is in the setup block
lens Ran
ran, honoured the contract we drafted
google-deepmind/open_spiel/open_spiel/python/algorithms/double_oracle.py
code served (permissive licence) · get_code("e893a592cd4dd8fe")
How it ran

Ran in Syntology's sandbox on this synthesized input (drafted by a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API) and returned list, ndim 1, dtype family int; no output shape is stated. The image it ran in was not recorded. If your copy returns the same type and ndim on these inputs, it matched what we observed; nothing here checks that. It does NOT mean the output is correct: nothing has compared it to the paper.

import torch

torch.manual_seed(0)

# The function lens() takes a parameter 'lists' which should be a list of lists
# and returns the length of each list. We need to provide a list of lists with
# different sizes to make the test meaningful.

ARGS = {
    "lists": [
        [1, 2, 3],
        [4, 5],
        [6, 7, 8, 9],
        []
    ]
}
Setup block drafted by
a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API
Imports
torch — import names as written, not package names to install; a name the repository itself provides is not a package
Returned
type list, ndim 1, dtype family int — a list output has no array shape of its own; none is stated
dtype family
int means an integer dtype; float means any other dtype the instrument saw, bool and complex included (fixture_check.py records only these two families)
Environment
image not recorded; re-verify against syntology-harvest-sandbox:v5-deps; not recorded for this sample: the harness installs a cuda-to-cpu shim (cuda_shim.py) before every sample and no run records whether a sample needed it; seed: none by the harness; any seed is in the setup block
max_child Ran
ran; our contract draft was wrong, not the code
google-deepmind/open_spiel/open_spiel/python/algorithms/async_mcts.py
code served (permissive licence) · get_code("df0219b92f616df8")
How it ran

Ran in Syntology's sandbox on this synthesized input (drafted by a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API) and returned tuple, ndim 1, dtype family float; no output shape is stated. The image it ran in was not recorded. If your copy returns the same type and ndim on these inputs, it matched what we observed; nothing here checks that. It does NOT mean the output is correct: nothing has compared it to the paper.

import math

class SearchNode(object):
    """A node in the search tree."""
    __slots__ = ['action', 'player', 'prior', 'explore_count', 'total_reward', 'outcome', 'children', 'expanded']

    def __init__(self, action: int | None, player: int, prior: float):
        self.action = action
        self.player = player
        self.prior = prior
        self.explore_count = 0
        self.total_reward = 0.0
        self.outcome = None
        self.children = []
        self.expanded = False

    def uct_value(self, parent_explore_count: int, uct_c: float) -> float:
        """Returns the UCT value of child."""
        if self.outcome is not None:
            return self.outcome[self.player]
        if self.explore_count == 0:
            return float('inf')
        return self.total_reward / self.explore_count + uct_c * math.sqrt(math.log(parent_explore_count) / self.explore_count)

    def puct_value(self, parent_explore_count: int, uct_c: float) -> float:
        """Returns the PUCT value of child."""
        if self.outcome is not None:
            return self.outcome[self.player]
        return (self.explore_count and self.total_reward / self.explore_count) + uct_c * self.prior * math.sqrt(parent_explore_count) / (self.explore_count + 1)

    def sort_key(self):
        """Returns the best action from this node, either proven or most visited."""
        return (0 if self.outcome is None else self.outcome[self.player], self.explore_count, self.total_reward)

    def best_child(self):
        """Returns the best child in order of the sort key."""
        return max(self.children, key=SearchNode.sort_key)

    def children_str(self, state=None):
        """Returns the string representation of this node's children."""
        return '\n'.join([c.to_str(state) for c in reversed(sorted(self.children, key=SearchNode.sort_key))])

    def to_str(self, state=None):
        """Returns the string representation of this node."""
        action = state.action_to_string(state.current_player(), self.action) if state and self.action is not None else str(self.action)
        return '{:>6}: player: {}, prior: {:5.3f}, value: {:6.3f}, sims: {:5d}, outcome: {}, {:3d} children'.format(action, self.player, self.prior, self.explore_count and self.total_reward / self.explore_count, self.explore_count, '{:4.1f}'.format(self.outcome[self.player]) if self.outcome else 'none', len(self.children))

    def __str__(self):
        return self.to_str(None)

def max_child(root: SearchNode) -> tuple[int, SearchNode]:
    """Returns the best action and associated child node."""
    selection_criteria = lambda node: node.total_reward / node.explore_count if node.explore_count else float('-inf')
    best_child = max(root.children, key=selection_criteria)
    return (best_child.action, best_child)


# Build root node with children
root = SearchNode(action=None, player=0, prior=1.0)

# Create child nodes with different exploration counts
child1 = SearchNode(action=0, player=1, prior=0.5)
child1.explore_count = 10
child1.total_reward = 5.0

child2 = SearchNode(action=1, player=1, prior=0.3)
child2.explore_count = 15
child2.total_reward = 9.0

child3 = SearchNode(action=2, player=1, prior=0.2)
child3.explore_count = 8
child3.total_reward = 3.0

root.children = [child1, child2, child3]

ARGS = {
    'root': root
}
Setup block drafted by
a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API
Imports
none outside the standard library — import names as written, not package names to install; a name the repository itself provides is not a package
Returned
type tuple, ndim 1, dtype family float — a tuple output has no array shape of its own; none is stated
dtype family
int means an integer dtype; float means any other dtype the instrument saw, bool and complex included (fixture_check.py records only these two families)
Environment
image not recorded; re-verify against syntology-harvest-sandbox:v5-deps; not recorded for this sample: the harness installs a cuda-to-cpu shim (cuda_shim.py) before every sample and no run records whether a sample needed it; seed: none by the harness; any seed is in the setup block
robust_child Ran
ran; our contract draft was wrong, not the code
google-deepmind/open_spiel/open_spiel/python/algorithms/async_mcts.py
code served (permissive licence) · get_code("5bb2db932067db4c")
How it ran

Ran in Syntology's sandbox on this synthesized input (drafted by a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API) and returned tuple, ndim 1, dtype family float; no output shape is stated. The image it ran in was not recorded. If your copy returns the same type and ndim on these inputs, it matched what we observed; nothing here checks that. It does NOT mean the output is correct: nothing has compared it to the paper.

import math

class SearchNode(object):
    __slots__ = ['action', 'player', 'prior', 'explore_count', 'total_reward', 'outcome', 'children', 'expanded']

    def __init__(self, action: int | None, player: int, prior: float):
        self.action = action
        self.player = player
        self.prior = prior
        self.explore_count = 0
        self.total_reward = 0.0
        self.outcome = None
        self.children = []
        self.expanded = False

    def uct_value(self, parent_explore_count: int, uct_c: float) -> float:
        if self.outcome is not None:
            return self.outcome[self.player]
        if self.explore_count == 0:
            return float('inf')
        return self.total_reward / self.explore_count + uct_c * math.sqrt(math.log(parent_explore_count) / self.explore_count)

    def puct_value(self, parent_explore_count: int, uct_c: float) -> float:
        if self.outcome is not None:
            return self.outcome[self.player]
        return (self.explore_count and self.total_reward / self.explore_count) + uct_c * self.prior * math.sqrt(parent_explore_count) / (self.explore_count + 1)

    def sort_key(self):
        return (0 if self.outcome is None else self.outcome[self.player], self.explore_count, self.total_reward)

    def best_child(self):
        return max(self.children, key=SearchNode.sort_key)

    def children_str(self, state=None):
        return '\n'.join([c.to_str(state) for c in reversed(sorted(self.children, key=SearchNode.sort_key))])

    def to_str(self, state=None):
        action = state.action_to_string(state.current_player(), self.action) if state and self.action is not None else str(self.action)
        return '{:>6}: player: {}, prior: {:5.3f}, value: {:6.3f}, sims: {:5d}, outcome: {}, {:3d} children'.format(action, self.player, self.prior, self.explore_count and self.total_reward / self.explore_count, self.explore_count, '{:4.1f}'.format(self.outcome[self.player]) if self.outcome else 'none', len(self.children))

    def __str__(self):
        return self.to_str(None)


def robust_child(root: SearchNode) -> tuple[int, SearchNode]:
    selection_criteria = lambda node: node.explore_count
    best_child = max(root.children, key=selection_criteria)
    return (best_child.action, best_child)


# Create a root node with some children
root = SearchNode(action=None, player=0, prior=1.0)

# Create child nodes with different explore counts
child1 = SearchNode(action=0, player=1, prior=0.3)
child1.explore_count = 5
child1.total_reward = 2.5

child2 = SearchNode(action=1, player=1, prior=0.4)
child2.explore_count = 10
child2.total_reward = 5.0

child3 = SearchNode(action=2, player=1, prior=0.3)
child3.explore_count = 3
child3.total_reward = 1.2

root.children = [child1, child2, child3]

ARGS = {
    'root': root
}
Setup block drafted by
a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API
Imports
none outside the standard library — import names as written, not package names to install; a name the repository itself provides is not a package
Returned
type tuple, ndim 1, dtype family float — a tuple output has no array shape of its own; none is stated
dtype family
int means an integer dtype; float means any other dtype the instrument saw, bool and complex included (fixture_check.py records only these two families)
Environment
image not recorded; re-verify against syntology-harvest-sandbox:v5-deps; not recorded for this sample: the harness installs a cuda-to-cpu shim (cuda_shim.py) before every sample and no run records whether a sample needed it; seed: none by the harness; any seed is in the setup block
robust_child_with_total_reward_tiebreaker Ran
ran; our contract draft was wrong, not the code
google-deepmind/open_spiel/open_spiel/python/algorithms/async_mcts.py
code served (permissive licence) · get_code("7fdee38eaebea0d2")
How it ran

Ran in Syntology's sandbox on this synthesized input (drafted by a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API) and returned tuple, ndim 1, dtype family float; no output shape is stated. The image it ran in was not recorded. If your copy returns the same type and ndim on these inputs, it matched what we observed; nothing here checks that. It does NOT mean the output is correct: nothing has compared it to the paper.

import math

class SearchNode(object):
    __slots__ = ['action', 'player', 'prior', 'explore_count', 'total_reward', 'outcome', 'children', 'expanded']

    def __init__(self, action: int | None, player: int, prior: float):
        self.action = action
        self.player = player
        self.prior = prior
        self.explore_count = 0
        self.total_reward = 0.0
        self.outcome = None
        self.children = []
        self.expanded = False

    def uct_value(self, parent_explore_count: int, uct_c: float) -> float:
        if self.outcome is not None:
            return self.outcome[self.player]
        if self.explore_count == 0:
            return float('inf')
        return self.total_reward / self.explore_count + uct_c * math.sqrt(math.log(parent_explore_count) / self.explore_count)

    def puct_value(self, parent_explore_count: int, uct_c: float) -> float:
        if self.outcome is not None:
            return self.outcome[self.player]
        return (self.explore_count and self.total_reward / self.explore_count) + uct_c * self.prior * math.sqrt(parent_explore_count) / (self.explore_count + 1)

    def sort_key(self):
        return (0 if self.outcome is None else self.outcome[self.player], self.explore_count, self.total_reward)

    def best_child(self):
        return max(self.children, key=SearchNode.sort_key)

    def children_str(self, state=None):
        return '\n'.join([c.to_str(state) for c in reversed(sorted(self.children, key=SearchNode.sort_key))])

    def to_str(self, state=None):
        action = state.action_to_string(state.current_player(), self.action) if state and self.action is not None else str(self.action)
        return '{:>6}: player: {}, prior: {:5.3f}, value: {:6.3f}, sims: {:5d}, outcome: {}, {:3d} children'.format(action, self.player, self.prior, self.explore_count and self.total_reward / self.explore_count, self.explore_count, '{:4.1f}'.format(self.outcome[self.player]) if self.outcome else 'none', len(self.children))

    def __str__(self):
        return self.to_str(None)


def robust_child_with_total_reward_tiebreaker(root: SearchNode) -> tuple[int, SearchNode]:
    selection_criteria = lambda node: (node.explore_count, node.total_reward)
    best_child = max(root.children, key=selection_criteria)
    return (best_child.action, best_child)


# Create a root node with children
root = SearchNode(action=None, player=0, prior=1.0)

# Create child nodes with different explore counts and total rewards
child1 = SearchNode(action=0, player=1, prior=0.5)
child1.explore_count = 10
child1.total_reward = 5.0

child2 = SearchNode(action=1, player=1, prior=0.3)
child2.explore_count = 10
child2.total_reward = 7.0

child3 = SearchNode(action=2, player=1, prior=0.2)
child3.explore_count = 5
child3.total_reward = 3.0

root.children = [child1, child2, child3]

ARGS = {
    "root": root
}
Setup block drafted by
a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API
Imports
none outside the standard library — import names as written, not package names to install; a name the repository itself provides is not a package
Returned
type tuple, ndim 1, dtype family float — a tuple output has no array shape of its own; none is stated
dtype family
int means an integer dtype; float means any other dtype the instrument saw, bool and complex included (fixture_check.py records only these two families)
Environment
image not recorded; re-verify against syntology-harvest-sandbox:v5-deps; not recorded for this sample: the harness installs a cuda-to-cpu shim (cuda_shim.py) before every sample and no run records whether a sample needed it; seed: none by the harness; any seed is in the setup block
strat_dict_to_array Ran
ran, honoured the contract we drafted
google-deepmind/open_spiel/open_spiel/python/algorithms/efr.py
code served (permissive licence) · get_code("7f99b0a7ffd18410")
How it ran

Ran in Syntology's sandbox on this synthesized input (drafted by a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API) and returned ndarray, ndim 2, dtype family float, shape (4, 1) as a later run recorded it. The image it ran in was not recorded. If your copy returns the same type, ndim and shape on these inputs, it matched what we observed; nothing here checks that. It does NOT mean the output is correct: nothing has compared it to the paper.

import numpy as np

# Create a simple strategy dictionary with action -> probability mappings
strategy_dictionary = {
    0: 0.1,
    1: 0.3,
    2: 0.4,
    3: 0.2
}

ARGS = {
    "strategy_dictionary": strategy_dictionary
}
Setup block drafted by
a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API
Imports
numpy — import names as written, not package names to install; a name the repository itself provides is not a package
Returned
type ndarray, ndim 2, dtype family float, shape (4, 1) — shape (4, 1) as a later run recorded it
dtype family
int means an integer dtype; float means any other dtype the instrument saw, bool and complex included (fixture_check.py records only these two families)
Environment
image not recorded; re-verify against syntology-harvest-sandbox:v5-deps; not recorded for this sample: the harness installs a cuda-to-cpu shim (cuda_shim.py) before every sample and no run records whether a sample needed it; seed: none by the harness; any seed is in the setup block

Also present in other papers' code

Of 7 samples lifted from this paper's linked repositories, 7 carry a function identity and 0 do not. Of the 7 distinct functions with an identity, 1 are also present in other papers whose code we hold (1 with at least one paper dated earlier, 0 the same month, 0 later) and 6 are only here among the 52,977 papers whose code Syntology holds (as of 2026-09-26).

Only here means: among the 52,977 papers whose code Syntology holds (51,887 with lifted samples, 1,090 through their assemblies only), as of 2026-09-26, no other paper's lifted samples or current assembly bricks contain an identical function body after normalisation.

FunctionAlso present inEarliest-datedOthers named
lens 2 other papers
2 dated earlier
1908.09453 (2019-08)
OpenSpiel: A Framework for Reinforcement Learning in Games
2402.19420 (2024-02)
Understanding Iterative Combinatorial Auction Designs via Multi-Agent Reinforcement Learning

Presence, not direction: an identical function body in two papers' repositories does not say who wrote it, which came from which, or that either paper's method rests on it. Matching is exact after normalisation, so a renamed or edited function is not matched. Dates are when papers appeared, not when code was written. Only .py files the harvester lifted are covered; notebooks are not read. A new-style arXiv id YYMM.NNNN dates a paper to the month 20YY-MM; otherwise Paper.year dates it to the year; otherwise it is undated. Dates are when the paper appeared, not when the code was written. Read 2026-11-22.

Repositories linked to this paper

Some links come from the archived Papers with Code dataset (CC BY-SA 4.0): attribution and licence.

Abstract

Robust Markov decision processes (MDPs) have attracted significant interest due to their ability to protect MDPs from poor out-of-sample performance in the presence of ambiguity. In contrast to classical MDPs, which account for stochasticity by modeling the dynamics through a stochastic process with a known transition kernel, a robust MDP additionally accounts for ambiguity by optimizing against the most adverse transition kernel from an ambiguity set constructed via historical data. In this paper, we develop a unified solution framework for a broad class of robust MDPs with s-rectangular ambiguity sets, where the most adverse transition probabilities are considered independently for each state. Using our algorithms, we show that s-rectangular robust MDPs with 1-and 2-norm as well as ϕ-divergence ambiguity sets can be solved several orders of magnitude faster than with state-of-the-art commercial solvers, and often only a logarithmic factor slower than classical MDPs. We demonstrate the favorable scaling properties of our algorithms on a range of synthetically generated as well as standard benchmark instances.

For agents

The same record, over MCP at https://syntology.ai/mcp:

get_harvested_code_for_paper("2602.05591")
get_code_for_paper("2602.05591")
have("2602.05591")

The run record, dated, one paper per request, free:

curl https://syntology.ai/api/ran/2602.05591.json

A badge for a README (the split and the date, never a ratio):

[![Syntology run record](https://syntology.ai/api/ran/2602.05591.svg)](https://syntology.ai/paper/2602.05591)

Connect an agent — have() is free.