IMED#

class statrl.settings.bandits.stochastic.anytime.agents.IMED.IMED(nbArms, kullback=<function klGauss>, name='IMED')[source]#

Bases: BanditAgent

Indexed Minimum Empirical Divergence, an asymptotically optimal bandit algorithm.

IMED assigns every arm the index

\[I_a(t) = N_a(t)\,\mathrm{kl}\!\left(\hat{\mu}_a(t), \hat{\mu}^\star(t)\right) + \log N_a(t)\]

and pulls the arm minimizing it. The first term is large for an arm whose empirical mean is confidently below the best one, the second penalizes arms already pulled often; minimizing their sum balances exploration against exploitation with no tuning parameter — no confidence level, no exploration bonus, no schedule.

The regret matches the Lai-Robbins lower bound asymptotically [1], provided kullback is the divergence of the true reward family.

Parameters:

nbArms (int) – Number of arms, which must equal env.number_arms.
kullback (callable, default=:func:~statrl.settings.utils.klGauss) – Divergence kl(x, y) between two means. Choose it to match the rewards: klBern() for Bernoulli, klGauss() for Gaussian or any sub-Gaussian reward. A mismatched choice costs the optimality guarantee but stays well defined.
name (str, default='IMED') – Label used in logfiles and plot legends. Give two IMED instances distinct names when comparing divergences in one experiment.

kl#

The divergence passed as kullback.

Type:: callable

nbDraws#

Number of pulls of each arm, \(N_a(t)\).

Type:: ndarray of shape (nbArms,)

cumRewards#

Cumulative reward collected from each arm.

Type:: ndarray of shape (nbArms,)

means#

Empirical mean of each arm, \(\hat{\mu}_a(t)\).

Type:: ndarray of shape (nbArms,)

maxMeans#

Best empirical mean, \(\hat{\mu}^\star(t)\).

Type:: float

indexes#

Current index of each arm; select_arm() minimizes over it.

Type:: ndarray of shape (nbArms,)

See also

statrl.settings.bandits.stochastic.batch.agents.BIMED.BIMED: The batched, distribution-free variant built on KLinf_threshold().
statrl.settings.markovdecisionprocess.discrete_nostructure.agents.IMED_RL.IMEDRL: The extension of the same index to ergodic MDPs.

Notes

Arms never pulled have index 0, the smallest value the index can take, so every arm is played once before any is repeated. Both a pull and an update cost \(O(K)\) time and \(O(K)\) memory.

References

Examples

>>> from statrl.settings.bandits.stochastic.anytime.envs.parametric import BernoulliBandit
>>> from statrl.settings.bandits.stochastic.anytime.interaction import BanditInteraction
>>> from statrl.settings.utils import klBern
>>> env = BernoulliBandit([0.2, 0.9, 0.5])
>>> agent = IMED(env.number_arms, kullback=klBern)
>>> scores = BanditInteraction().run(env, agent, horizon=500)
>>> int(agent.nbDraws.argmax())          # the best arm is pulled most often
1

Methods

`__init__`(nbArms[, kullback, name])
`reset`()	Clear every statistic before a new independent run.
`select_arm`([state])	Pull the arm of minimal IMED index, \(\arg\min_a I_a(t)\).
`update`(arm, reward)	Refresh the empirical means and recompute every index.

reset()[source]#

Clear every statistic before a new independent run.

Counts, cumulative rewards, means, and indexes are all zeroed, so all arms start tied and each is pulled once before any repeat.

select_arm(state=0)[source]#

Pull the arm of minimal IMED index, \(\arg\min_a I_a(t)\).

Parameters:: state (int, default=0) – Ignored; a bandit has no state. Accepted so the agent also fits the state-passing signature used in the MDP settings.
Returns:: Index of the selected arm. Ties are broken uniformly at random by randmin(), which matters at the start of a run when every index is still 0.
Return type:: int

update(arm, reward)[source]#

Refresh the empirical means and recompute every index.

Increments the pull count and cumulative reward of arm, updates its empirical mean and the running best mean, then recomputes \(I_a(t)\) for all arms — all of them, because they share \(\hat{\mu}^\star(t)\).

Parameters:

arm (int) – Index of the arm that was pulled.
reward (float) – Reward observed for that arm.