Model-Based Exploration in Monitored Markov Decision Processes
Authors: Alireza Kazemipour
Matthew E. Taylor
Michael Bowling
Venue: ICML 2025 poster (2025)
Keywords: Exploration-Exploitation
Model-Based Interval Estimation
Monitored Markov Decision Processes
Primary area: reinforcement_learning
TL;DR: This paper introduces a model-based algorithm for sequential decision-making in the face of partially observable rewards.

Abstract: A tenet of reinforcement learning is that the agent always observes rewards. However, this is not true in many realistic settings, e.g., a human observer may not always be available to provide rewards, sensors may be limited or malfunctioning, or rewards may be inaccessible during deployment. Monitored Markov decision processes (Mon-MDPs) have recently been proposed to model such settings. However, existing Mon-MDP algorithms have several limitations: they do not fully exploit the problem structure, cannot leverage a known monitor, lack worst-case guarantees for "unsolvable" Mon-MDPs without specific initialization, and offer only asymptotic convergence proofs. This paper makes three contributions.  First, we introduce a model-based algorithm for Mon-MDPs that addresses these shortcomings. The algorithm employs two instances of model-based interval estimation: one to ensure that observable rewards are reliably captured, and another to learn the minimax-optimal policy. Second, we empirically demonstrate the advantages. We show faster convergence than prior algorithms in more than four dozen benchmarks, and even more dramatic improvements when the monitoring process is known. Third, we present the first finite-sample bound on performance. We show convergence to a minimax-optimal policy even when some rewards are never observable.

Model-Based Exploration in Monitored Markov Decision Processes
Alireza Kazemipour 12 Matthew E. Taylor 1 Michael Bowling 123
Abstract
alistic because feedback often comes from an exogenous entity, such as humans (Shao et al., 2020; Hejna & Sadigh, 2024) or monitoring instruments (Vu et al., 2021). Assum- ing the reward is available at all times is not reasonable in such settings, e.g., due to human time constraints (Pi- larski et al., 2011), 1), hardware failure (Bossev et al., 2016; Dixit et al.. 2021), 1), or inaccessible rewards during deploy- ment (Andrychowicz al., 2020). Hence, relaxing the assumption that rewards always observable would mark significant step toward agents continually operating in the real world. As an extension of Markov decision pro- cesses (MDPs), monitored Markov decision processes (Mon- MDPs) (Parisi et al., 2024b) have been proposed to model such situations, although algorithms for Mon-MDPs remain in their infancy (Parisi al., 2024a). Existing algorithms do not leverage the structure of Mon-MDPs, focusing ex- ploration uniformly across the entire state-action space, and only have asymptotic guarantees without providing sample complexity bounds. Furthermore, they have focused on solv- able Mon-MDPs, where observing every reward under some cireumstances possible. The original introduction of Mon- MDPs also considered unsolvable Mon-MDPs, proposing a minimax formulation as the optimal behavior, but no algo- rithms have explored this setting.
A tenet of reinforcement learning is that the agent always observes rewards. However, this is not true in many realistic settings, e.g., human ob- server may not always be available to provide rewards, sensors may be limited or malfunction- ing, or rewards may be inaccessible during de- ployment. Monitored Markov decision processes (Mon-MDPs) have recently been proposed to model such settings. However, existing Mon- MDP algorithms have several limitations: they do not fully exploit the problem structure, can- not leverage a known monitor, lack worst-case guarantees for "unsolvable" Mon-MDPs without specific initialization, and offer only asymptotic convergence proofs. This paper makes three con- tributions. First, we introduce model-based algo- rithm for Mon-MDPs that addresses these short- comings. The algorithm employs two instances of model-based interval estimation: one to ensure that observable rewards are reliably captured, and another to learn a minimax oppiimal policy. Sec- ond, we empirically demonstrate the advantages. We show faster convergence than prior algorithms in more than four dozen benchmarks, and even more dramatic improvements when the monitor- ing process is known. Third, we present the first finite sample-bound on performance. We show convergence to a minimax-optime policy even when some rewards are never observable.
In this paper, we introduce Monitored Model-Based Inter- val Estimation with Exploration Bonus (Monitored MBIE- EB), a mosel-based algorithm for Mon-MDPs that offers several advantages over previous algorithms. Monitored MBIE-EB exploits the Mon-MDP structure to consider the uncertainty on each unknown component separately. This approach also makes it the first algorithm that can take ad- vantage of situations where the agent knows the monitoring process in advance. Furthermore, Monitored MBIE-EB balances optimism in uncertain quantities with pessimism for rewards that have never been observed, reaching the minimax opptimll behavior in unsolvable Mon-MDPs. The trade-off between optimism and pessimism is challenging because pessimism may dissuade agents from exploring suf- ficiently in solvable Mon-MDPs. We address this by having second instance of MBIE-EB to force the agent to effi- ciently observe all rewards that can be observed. Building off of MBIE-EB (Strehl & Littman, 2008), we prove the first polynomial sample complexity bounds (Kakade, 2003; Lattimore & Hutter, 2012) as the measure of Monitored
1. Introduction
Reinforcement learning (RL) is based on trial-and-error: in- stead of being directly shown what to do, agent receives consistent numerical feedback in the form of rewards for its decisions. However, this assumption is not always re-
'Department of Computing Science, University of Alberta 2 Alberta Machine Intelligence Institute (Amii) 'Canada CIFAR Al Chair, Amii. Correspondence to: Alireza Kazemipour < Dicemip@@uabeetta.c..
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Model-Based Exploration in Mon-MDPs
MBIE-EB's efficiency, which applies equally to solvable and unsolvable Mon-MDPs. We then explore the Monitored MBIE-EB's ' efficacy empirically, We present its efficient exploration in practice, outperforming the recent Directed Exploration--Exploitation algorithm (Parisi et al., 2024a) in four dozen benchmarks, including all of environments from Parisi et al. (2024a). We also demonstrate that Moni- tored MBIE-EB converges to optimal policies in solvable Mon-MDPs and minimax-optimal policies in unsolvable Mon-MDPs. This confirms Monitored MBIE-EB is able to separate the solvable Mon-MDPs from the unsolvable ones. Finally, we illustrate Monitored MBIE-EB can exploit knowledge of the monitoring process to learn even faster.
Environment
Environment
A
R
1"
Monitor
S*
t
R
R
5
Agent
Agent
(a) MDP framework
(b) Mon-MDP framework
Figure 1: In MDPs (left) the agent interacts only with the environment and observes rewards at all times. In Mon- MDPs (right), the agent also interacts with the monitor, which dictates what rewards the agent observes. For clarity, we have omitted the dependence on time from the notation.
2. Preliminaries
Traditionally, RL agent-environmenn interaction is modeled as Markov decision process (MDP) (Puterman, 1994; Sut- ton& & Barto, 2018): at every timestep the agent performs an action A, according to the environment state St; in turn, the environment transitions to a new state S and gener- ates a bounded numerical reward R4+1- It is assumed that the agent always observes the rewards. Any partial observ- ability is only considered for environment states, resulting in partially observable MDPs (POMDPs) (Kaelbling al., 1998; Chadès et al., 2021). Until recently, prior work on par- tially observable rewards was limited to active RL (Schulze & Evans, 2018; Krueger et al., 2020), RL from human feedback (RLHF) (Kausik et al., 2024), options frame- work (Machado Bowling, 2016), and reward-uncertain MDPs (Regan & Boutilier, 2010). However, these frame- works lack the complexity to formalize situations where the reward observability stems from some stochastic processes. In active RL, the reward can always be observed by simply paying a cost; in RLHF, the reward is either never observ- able (with no guidance coming from the human) or always observable (with the human providing all the guidance). Neither of these settings capture scenarios, where there are rewards that the agent can only sometimes see and whose observability can be predicted and possibly controlled.
methods that attempt to model the process governing reward observability in order plan which rewards to observe, or which states visit where rewards are more likely to be observed. In the next sections, we 1) revisit Mon-MDPs as an extension of MDPs, 2) define minimaxx-optimalin when some rewards may never be observable, and 3) highlight how our algorithm addresses existing limitations.
2.1. Monitored Markov Decision Processes
MDPs are represented by the tuple (S, 7). where S is the finite state space, A is the finite action space, r : S A + frimig rfmxd] is the mean reward function, p S x A - (S)) is the Markovian transition dynamics, and 7 E 10,1) is the discount factor describing the trade-off between immediate and future gains. Mon-MDPs extend MDPs by introducing the monitor, another entity that the agent interacts with and is also governed by Markovian transition dynamics. Intuitively, Mon-MDPs incorporate two MDPs - one for the environment and one for the monitor - and we differentiate quantities associated with each using superscripts "e" and "m", respectively.
In Mon-MDPs, the state and the action spaces comprise the environment and the monitor spaces, i.e., S = S x Sth and A := A4 x AAT. At every timestep, the agent observes the state of both the environment and the monitor, and performs a joint action. The monitor also has Markovian dynamics, i.e., pm S x A x S A + A(8"), and the joint transition dynamics is denoted by p pf pm SS x A + (SS) Note that the monitor transition dynamics depend on the environment state and action, highlighting the interplay between the monitor and the environment.
Recently, inspired by partial monitoring (Bartók et al., 2014), Parisi et al. (2024b) extended the MDP framework to also consider partially observable rewards by proposing the Monitored MDP (Mon-MDP). In Mon-MDPs, the ob- servability of the reward is dictated by "Markovian entity" (the monitor). Thus, actions can have either immediate or long-term effects on the reward observability. For example, rewards may become observable only when certain condi- tions are met - such as when the agent presses a button in the environment, carries a special item, or operates in areas equipped with instrumentation. The control over ob- servability of the reward opens avenues for model-based
Mon-MDPs also have two mean rewards, r = -(r, ")) where Tm ST A + [rmin max] is also bounded (To reduce the clutter only in the theoretical part of this
work, assume riin := max = - and y. --- max
We denote random variables with capital letters
AA(X') denotes the set of distributions over the finite set
2

---

Model-Based Exploration in Mon-MDPs
tried many times, it seems I will never observe its outcooe!!
outeamie could a smake! I will not tyy LEFE
outcome not suike, but will never know. safe than surrs!
(a) LEFT's outcome cannot be observed and will always be unknown.
(b) A pessimistic agent assumes the worst (snake) for LEFT.
(c) The agent would be pessimistic even if LEFT'ss true outcome is not the snake.
Example of a pessimistic agent in Mon-MDPs, RIGHT leads to a snake, UP to gold bars, and LEFT to either a snake or treasure chest (more valuable than gold bars), but the agent can never observe the result of executing LEFT. (b) After sufficient attempts", the agent excludes LEFT because its outcome is unknown and the agent assumes the worst. (c) LEFT is ruled out, even though it could actually yield the treasure chest. However, since this cannot be known, acting pessimistically complies with minimax-optimality in Equation (3). In the end, the agent explores new actions but it is also wary because some actions may never yield a reward. Thus, after enough exploration, it assumes the worst if the action's ' outcome is still unknown.
Figure 2:
(a) The agent has to choose between LEFT, UP, and RIGHT.
-)). However, unlike classical MDPs, the environment re- wards are not directly observable. Instead, at a timestep t in place of the (possibly stochastic) environment reward R++1 I., the agent observes the proxy reward R +1 f (RC 11 ST A.).. where fm R x St x A - IR (1) is the monitor function and 1 denotes an "unobserved re- ward", i.e., the agent does not receive any numerical reward?. Using the above notation, a Mon-MDP M can be compactly denoted by the tuple M = (S, r,,, f 7)- Figure illustrates agent-nnviromment-omiic
at all times for some state-actions. For example, consider task where human supervisor (the monitor) gives the reward: if the supervisor leaves, the agent will not observe any reward anymore; yet, the task has not changed, i.c., the human - present would still give the same rewards.
2.2. Learning Objective in Mon-MDPs
In this section, define the state-values and action-values for Mon-MDPs. Further, we define the learning objective as finding minimax-optimal policy. Let P and IE be the probability measure and expectations we get when a policy т is run in M starting from an initial state. Similar to MDPs, the state-value V and action-valle Q3 denote the expected sum of discounted rewards, with an optimal policy nt maximizing them:
interaction.
In Mon-MDPs, at timestep Ê the agent executes the joint action A, == (49, AT)) at the joint state S, = (S), In turn, the environment and monitor states change and produce a joint reward (Re+1, 1. but the agent ob- serves (Ri+1,11T4)) The agent's 's goal is to learn policy =SS- --> ((A) selecting joint actions to maximize the expected* discounted return E O (Ri+1 + 1)], even though the agent observes R2+1 instead of RT-1. This is the crucial difference between MDPs and Mon-MDPs: the immediate environment reward R is always generated by the environment, i.e., desired behavior is well-defined as the reward sufficient to describe the agent's 's task (Bowling al., 2023). Yet, the monitor may "hide it" from the agent, possibly even yielding "unobservable reward" R
(s) = E
R8+1
S =
(7r(s, == E
R
St 8,=
=
V E sup (s),,), nEnl
WsES,
(1)
where RA+1 = R2+1 R is the immediate joint re- ward at timestep h and II is the set of policies in M. We stress once more that the agent cannot observe the imme- diate environment reward Ri_ directly and observes the
'Note that 1r could return any arbitrary real number, unrelated to the environment reward. To rule out pathological cases (c.g., the monitor function always returns 0), f assumed be truth- ful (Parisi et al., 2024b), i.c., the monitor either reveals the true environment reward (Ri,1 R) or hides (f L).
'We define "sufficient" in Theorem 3.1. Intuitively, the confident the agent wants to be, the more it should try the action.
"Section 2.2 defines the reference measure for the expectation.
3

---

Model-Based Exploration in Mon-MDPs
immediate proxy reward N4 for all k 2 0, even though the environment still assigns rewards to the agent's actions.
equivalent to Equation (1). Therefore, the minimax-optimal policy is simply the optimal policy. Figure 2 shows an unsolvable Mon-MDP and the minimax-optimal policy.
Parisi et al. (2024a) showed asymptotic convergence to an optimal policy with an ergodic monitor function f", i.e., for all environment state-action pairs (s",a"), there exists at least a monitor state-action pair (s"", ad") such that the proxy reward is observed infinitely-ofier given infinite exploration. (s', s"
3. Monitored Model-Based Interval Estimation
We propose a novel model-based algorithm to exploit the structure of Mon-MDPs, show how to apply it on solvable and unsolvable Mon-MDPs, and provide sample complexity bounds. As our algorithm builds upon MBIE and MBIE- EB (Strehl & Littman, 2008), we first briefly review both.
Formally, let
and a (a aeeaa))) aa).. then
P lim sup T # S. 8, A = >0. 0. (-000
Intuitively, this means the agent will always be able to observe every environment reward (infinitely many times, given infinite cxploration). However, if even one environ- ment reward is never observable, the Mon-MDP is unsoly- able, and convergence to an optimal policy cannot be guar- anteed. Essentially, if the agent can never know that spe- cific state-action yields the highest (or lowest) environment reward, then it can never learn to visit (or avoid) it. Nonethe- less, we argue that assuming every environment reward is observable (sooner or later) is a very stringent condition, not suitable for real-world tasks - reward instrumentation may have limited coverage, human supervisors may never be available in the evening, or training before deployment may not guarantee full state coverage.
3.1. MBIE and MBIE-EB
MBIE is an algorithm for learning optimal policy in MDPs with polynomial sample complexity. MBIE main- tains confidence intervals on all unknown quantities (i.e., mean rewards and transition dynamics) and solves the set of corresponding MDPs to produce an optimistic value func- tion. Greedy actions with respect to this value function direct the agent toward insufficiently visited state-action pairs to be certain whether they are part of the optimal pol- icy or not. MBIE-EB is a simpler variant that constructs a single confidence interval around the action-values (instead of building confidence intervals around the mean rewards and transitions separately) with an exploration bonus to be optimistic with respect to the uncertain quantities.
To define the learning objective even in unsolvable Mon- MDPs, we follow Parisi et al. (2024b, Appendix B.3). First, let [M] be the set of all Mon-MDPs the agent cannot dis- tinguish based on the reward observability M. That is, all Mon-MDPs with identical state and action spaces, transition dynamics and monitor function to M, but differing in their environment mean reward re (for the full definition see Ap- pendix H). If M's is solvable, all rewards can be observed and [M] = {M i.e., the set of indistinguishable Mon-MDPs to the agent is a singleton. Otherwise, from the agent's 's perspective, there are possibly infinitely many Mon-MDPs in [M] because the underlying never-observable rewards' mean could be any real value within their bounded range. Second, let M, be the worst-case Mon-MDP, i.e., the one whose all never-observable rewards are "mmn"
Let R and P be maximum likelihood estimates of the MDP's unknown mean rewards and transition dynamics based on the agent's experience, and let N(s, a) count the number of times action has been taken in state s. MBIE-EB constructs an optimistic MDP4,
R(s, = R(s, + VN(s,a) a
P P=
(4)
bonus for vn
where 3 is a parameter chosen to be sufficiently large. solves the MDP (using value iteration) to find Q, the optimal action-value under the model, and acts greedily with respect to this function to gather more data to update its model.
Mi E argmin "h (s", V(s", S S (2) M'E[M]
3.2. Monitored MBIE-EB
where rh is the environment mean reward in M'. In words, M, is Mon-MDP whose mean environment reward is minimized over all Mon-MDPs indistinguishable from M. Then, we define the minimax-optinal policy of M as the optimal policy of the worst-case Mon-MDP, i.e.,
Monitored MBIE-EB can be considered an extension of MBIE-EB to the Mon-MDPs with three key innovations. First, we adapt MBIE-EB to model each of the vital un- known components of the Mon-MDP (mean rewards and transition dynamics of both the environment and the mon- itor), each with their own exploration bonuses. Second, observing that the optimism for unobservable environment state-action pairs in an unsolvable Mon-MDP will never
V E sup FEll
VM (s),
Vs E S,
(3)
where II is the set of all policies in Mj. As noted earlier, if M is solvable then [M] = (M), and Equation (3) is
'In this work, the denominator of bonuses starts one; if zero, optimistic initialization used unless otherwise stated.
4

---

Model-Based Exploration in Mon-MDPs
vanish- the agent will try forever observe rewards that actually unobservable- we further adapt the algorithm to make worst-case assumptions all unobserved envi- ronment rewards. Unfortunately, this creates an additional problem: environment state-action pairs whose rewards are hard to observe may never be sufficiently tried because they are dissuaded by the pessimistic model. Third, to balance the aetimism-drivens exploration and the pessimism induced by the worst-case assumption, Monitored MBIE-EB inter- leaves a second MBIE-EB instance that ensures unobserved environment state-actions are sufficiently explored.
We call an episode where we take greedy actions accord- ing Qun an optimize episode, as this ideally produces minimax-optimal policy for all Mon-MDPs. The reader may have already realized this pessimism will introduce a new problem - dissuading the agent from exploring to ob- serve previously unobserved environment rewards. Instead, we aim to observe all rewards but not too frequently that we prevent the agent from following the dinimax-optimal policy when the Mon-MDP is actually unsolvable.
Third Innovation:
Explore to Observe Rewards. We fix this now excessive pessimism by introducing a sepa- rate MBIE-EBB-uidee exploration aimed at discovering pre- viously unobserved environment rewards. The following reward model does exactly that. Let Il (N((""a""=)) be the indicator function returning one if (s (,,, ) equal to zero and returns zero otherwise, then Raos (s, a)
First Innovation: Extend MBIE-EB to Mon-MDPs. Let Re RR, PP be maximum likelihood estimates of the envi- ronment mean reward, monitor mean reward, and the joint transition dynamics, respectively, all based on the agent's 's ex- perience. Let N N(" a²)) count the number of times action a has been taken in sh N(s, a) count the same joint state- action pairs, and (ss aa) count environment state-action pairs, but only if the environment reward was observed. We then construct the following optimistic MDP using reward bonuses for the unknown estimated quantities,
KL-UCB (0, (s,, a)) [()(++,0 VNC.,))
(8)
Therefore, the KL-UCB (Garivier & Cappé, 2011; Maillard et al., 2011) term is only included for environment state- action pairs whose rewards have not been observed. Let d be the relative entropy between two Bernoulli distributions and GKL.UCB be a positive constant, then KL-UCB n) =
bonus For yd
g
Brasic (a, a) = (s ,d) +
SKL-UCB
N(x (80, a²) 3m
max P
p [0, :((;()) S
n
p=0
AT (s" am +
/N(s am)
NN a)
J E (0, 1]:11]11 In
1
KKL-UCB
max
n1
bonus for pd
bonus for p
We are using KL-UCB to estimate an upper-confidence bound (with parameter gKL-UCB) on the probability of ob- serving the environment reward from joint state-action (s, a) given that we have tried it N(ss, a) times already and have not succeeded to observe the reward (zero the first argu- ment of KL-UCB in Robs indicates this lack of success). As we are constructing a upper confidence bound on a Bernoulli random variable (whether the reward is observed or not), KL-UCB is ideally suited and provides tight bounds. The result is an optimistic model for an MDP (built based on the joint Mon-MDP, where Rob. is the mean reward) that rewards the agent for observing previously unobserved envi- ronment rewards. An episode where we take greedy actions with respect to Qots we call an observe episode. If we have enough observe episodes, we can guarantee that all observ- able environment rewards are observed with high probability. If we have enough optimize episodes we can learn and fol- low the minimax-optimal policy. We balance between the two by switching the model we optimize according to
P=P.
(5)
where B, 3 3ThH are hyperparameters for the confidence level of our optimistic model. As with MBIE-EB, this op- timistic model is solved to find Q and actions are selected greedily. For solvable Mon-MDPs, MBIE-EB's theoretical results apply directly to the joint Mon-MDP, yielding a sam- ple complexity bound. But, this algorithm fails to make any guarantees for unsolvable Mon-MDPs, where some envi- ronment rewards are never-observable. In such situations, N(s*, a never grows for some state-actions, thus opti- mism will direct the agent seek out these state-actions, for which it can never reduce its uncertainty.
Second Innovation: Pessimism Instead of Optimism. We fix this excessive optimism in Equation (5) by creating new reward model that is pessimistic, rather than optimistic, about unobserved environment state-action rewards:
Rspi(s, a) = Rrasic (s, a), if ((s aa) > 0,
(6)
Ruiin a),
otherwise,
A(s.a) = Rons a), if S n*(K);; (x, a)) otherwise;
(9)
where Rmin (s, a) =
where R² is a sublinear function returning how many episodes of the ls total episodes should have been used to ob- serve and is the number of episodes that have been used to
gm
9
T + R= as
+
(7)
/ NN(s am VN(s,a)
5

---

Model-Based Exploration in Mon-MDPs
observe. The choice of K* is a hyperparameter. Monitored MBIE-EB then constructs the R(s,a), ) model and selects greedy actions with the respect to its optimal action-value Q. The choice to hold the policy fixed through- out the course of an episode is matter of simplicity, giving easier analysis that observe episodes will observe environ- ment rewards, as well computational convenience.
The reader may refer to Appendix G for the proof.
An interesting addition to the bound over MBIE-EB bound for classical MDPs is the dependence on the p's inverse, which bounds how difficult it is to observe the observable environment rewards. If Mon-MDP does reveal all rewards (it is solvable) but only does so with infinitesimal probability, an algorithm must be suboptimal for many more timesteps. In Appendix in a simpler setting of stochastic bandit problem with finitely many arms and partially observable re- wards by providing lower bound, we show the dependence of Theorem 3.1's bound on p is essentially unimprovable.
3.3. Theoretical Guarantees
One measure of RL algorithms' efficiency is their finite- time sample complexity, i.e., the number of timesteps (de- cision) required for the algorithm to find a near-desired policy with high probability (Kakade, 2003; Strehl et al., 2009; Lattimore & Hutter, 2012). Monitored MBIE-EB has polynomial sample complexity (with respect to the relevant parameters) even in unsolvable Mon-MDPs. There exists parameters where the algorithm guarantees with high probability (1 (1- of being arbitrarily close (c) to a minimax- optimal policy for all but a finite number of timesteps, which is a polynomial of 1, 8+ and other quantities characterizing the Mon-MDP. Theorem 3.1 establishes the sample com- plexity of Monitored MBIE-EB, the first sample complexity bound for Mon-MDPss is a unification of necessary new propositions that extend the analysis of MBIE-EB (Strehl & Littman, 2008, Theorem 2) to
3.4. Practical Implementation
The theoretically justified parameters for Monitored MBIE- EB present a couple of challenges in practice. First off, we rarely have a particular ε and 5 in mind, preferring algo- rithms that produce ever-improving approximations with ever-improving probability. Second, the bound, while poly- nomial in the relevant values, does not suggest practical parameters. The most problematic in this regard is the con- stant k", which places all observe episodes at the start of training. Third, solving model exactly and from scratch each episode to compute Q is computationally wasteful.
In practice we slowly increase the confidence levels used in the bonuses over time. We follow the pattern of Lattimore & Szepesvári (2020), with the confidence growing slightly faster than logarithmically" The scale parameters B, 8r S gobs, ,KLLLUBB were tuned manually for each environment. For X* we also grow it slowly over time allowing the agent to interleave observe and optimize episodes: n² x**) log k where the log base was also tuned manually for each en- vironment. Finally, rather than exactly solving the models every episode, we maintain two action-values: Qohs and Qupt both initialized optimistically. we do 50 steps of syn- chronous value iteration before every episode to improve Qupt. and before every observe episodes to improve Q Qoes.
Theorem 3.1. For any E, 8 > O, and Mon-MDP M where is the minimum non-zero probability of observing the environment reward in M and H is the maximum episode length, there exists constants mi, my, and my where
SSI
m1 0
E2
7/4
m2 δ
(1 - 72
|s| IA|
mg δ
E3(1 -7)5
such that Monitored MBIE-EB EB with parameters,
4. Empirical Evaluation
B 2
22 In (5 [8| |A| m2/8),
This paper began by detailing limitations in prior work not leveraging the Mon-MDP structure, the possibility of a known monitor, nor dealing with unsolvable Mon-MDPs. This section breaks down this claim into four research ques- tions (RQ) to investigate if Monitored MBIE-EB can: RQI) Explore efficiently in hard-exploration tasks? RQ2) Act pes- simistically when rewards are unobservable? RQ3) Identify
7
8 V 2 In (5| |A| m2/5),
8 / / In (5|8) A m2/0),
gohs (1 7) V In [8) |A| ml/36),
BKL-UCB In (10 ||] m1/3)),
(*k)) = M3,.
(constant function)
We replace / with 8 [I N(s)), where g(x) = 1 + xe (x: and N(s) counts the number of visits to state 8. This choice of is required as rewards and state-values are unlikely to follow Gaussian distribution, but being bounded allows us to assume they are sub-Gaussian. We similarly grow ,5", and gobs and replace gKL.UCB with gELUCH g(n N (s)).
provides the following bounds for M. Let denote Mon- itored MBIE-EB's 's policy and St denote the state at time t. With probability at least 1 1- 8. VIT (S.) 2 V - E for all
but 3 ( |S| |A| H
63 - p) timesteps.
6

---

Model-Based Exploration in Mon-MDPs
Monitored MBIE-EB
Directed-E?
Known Monitor
Minimax-Optimal
Discounted Test Return
20.0
0.0
0.
(a) River Swim
15.0
-100.0
-4.
-200.0-
T
5.8
300.0
-0.
13
20
10
10
36
16
Training Steps (x10")
Training Steps (x1))"
Training Steps (x 10")))
Training Steps (x10²)
T
(a) River Swim
(b) Bottleneck (100%)
(c) Bottleneck (5%)
(d) Bottleneck (5%)
T
Figure 4: Discounted return at test time, averaged over 30 seeds (shaded areas denote 95% confidence intervals). Monitored MBIE-EB (in green) outperforms Directed-B" (in orange) and always converges to the camiimax--ptimlll policy (the dashed black line). (c) and (d) both show results in the Bottleneck with the 5% Button Monitor, but with different axis ranges to highlight the improvement if Monitored MBIE-EB already knows details of the monitor (in purple).
(b) Bottleneck
Figure 3: Environments
and learn about difficult to observe rewards? RQ4) Take advantage of known model of the monitor?
the treasure chest, while avoiding the snake and 1 states, and turning the monitor OFF it was ON at the beginning of the episode. To evaluate Monitored MBIE-EB when ob- servability is stochastic, we consider two Button Monitors: one where the monitor works intended and rewards are observable with 100% probability if ON, and a second where the rewards are observable only with 5% probability if ON.
To directly address these questions, we first show results on two tasks with two monitors. Then, we show results on 48 benchmarks to strengthen our claims*.
4.1. Environment and Monitor Description
River Swim (Figure 3a) a well-known difficult exploration task with two actions. Moving LEFT always succeeds, but moving RIGHT may not the river current may cause the agent to stay at the same location or even be pushed to the left. There is a goal state on the far right, where moving right yield a reward of 1. But, the leftmost tile yields 0.1 and it is casier to reach. Other states have zero rewards. Agents often struggle to find the optimal policy (always move RIGHT), and instead converge to always move LEFT. In our experiments, we pair River Swim with the Full Moni- for where environment rewards are always freely observable, allowing us to focus on an algorithm's 's exploration ability.
4.2. Results
We evaluate Monitored MBIE-EB compared to Directed Exploration-Exploiae
(Directed-E") (Parisi et al., 2024a), which is currently the most performant algorithm in Mon- MDPs. The discount factor is fixed to 0.99, Appendix E. contains the set of hyperparameters and Appendix B con- tains the evaluation details (e.g., episodes lengths, etc). Re- sults in Figures 4 and are at test time, i.c., when the agent follows the current greedy policy without exploring.
To answer RQ1, consider the results in Figure 4a. Monitored MBIE-EB significantly outperforms Directed-E22. This task is difficult for any s-greedy exploration strategy (such as the Directed-EE and highlights the first innovation: taking a model- approach in Mon-MDPs (i.e., extending MBIE. EB) leads more efficient exploration.
Bottleneck (Figure 3b) has five deterministic actions: LEFT, UP, RIGHT, DOWN, STAY, which move the agent around the grid. Episodes end when the agent executes STAY in either the gold bars state (with a reward of 0.1) or in the treasure chest state (with reward of 1). Reaching the snake state yields -10, and other states yield zero. However, states denoted by 1 have never-observable rewards of - 10, i.e., 18 = 10 but Ri = 1. at all times t. In our experiments, we pair Bottleneck with the Button Monitor, where the monitor state can be CN or OFF (initialized at random) and is switched if the agent executes DOWN in the button state. When the monitor is ON, the agent receives R -02 at every timestep f, but also observes the cur- rent environment reward (unless the agent is in I. state). The minimax-optimal policy follows the shortest path to
To answer RQ2, consider Figure 4b. States marked with 1 are never observable by the agent, regardless of the moni- tor state. Because the minimum mean reward in this task is Tmin = 100 the minimax-optimal policy is to avoid states marked by 1 while reaching the goal state. Moni- tored MBIE-EB is able to find this minimax optimaal policy, whereas Directed-E2 does not because it does not learn to avoid unobservable rewards". This result highlights the
"DrecteddE2 describes initializing its reward model randomly, relying on the Mon-MDP being solvable, independent the initial- ization. For unsolvable Mon-MDPs this is not true and Directed-PP EE2 depends significantly initialization. In fact, while not noted
*Code:
Mr
7

---

Model-Based Exploration in Mon-MDPs
Visitation Count
1.0
40
Monitored MBIE-EB
Dírected-E2
0.0
Figure Visits to important states at test time in the Bottleneck with 5% Button Monitor. Results are averaged over 30 trials, and shaded areas denote 95% confidence interval. Directed-E2 fails to focus on the goal and instead keeps visiting 1 states, whereas Moni- tored MBIE-EB reduces its visitation frequency instead, ultimately visiting only the goal.
10
20
10
Training Steps (x 100))
Training Steps (x10P)
(a) Visits the goal
(h) Visits to 1.
impact of the second innovation:
unsolvable Mon-MDPS require pessimism when the reward cannot be observed.
explains why Directed-E" performs even worse in Figure 4c.
Finally, Figure 6 presents results comparing Monitored MBIE-EB across all of the domains and monitor bench- marks from Parisi al. (2024a). In these 48 benchmarks, Monitored MBIE-EB significantly outperforms Directed-E in all but five of them, where they perform similarly.
To answer RQ3, consider Figure 4c, where the Button Mon- itor provides a reward only 5% of the time when ON (and 0% of the time when OFF). Despite how difficult it is to observe rewards, Monitored MBIE-EB is able to learn the minimax-optimal policy. This shows that Monitored MBIE- EB is still appropriately pessimistic, successfully avoiding I states and the snake, and reaching the goal state. Since rewards are only visible one out of twenty times (when the monitor is ON), learning is much slower than in Figure 4b, matching the appearance of p in Theorem 3. I's bound. This result also shows the impact of the third innovation: it is important to explore just enough to guarantee the agent will learn about observable rewards, but no more.
5. Discussion
There are a number of limitations to our approach suggesting directions for future improvements. First, Mon-MDPs con- tain an
dilemma, but with an added twist - the agent needs to treat never observed rewards pessimistically to achieve minimax-optimalin should continue exploring those states to get more confident about their unobservability. Much like early algorithms for the exploration-exploitatioo exploitation dilemma in MDPs (Kearns & Singh, 2002), our approach separately optimizes a model for exploring and one for seeking minimax- optiimaaattttimittyy......m A more elegant approach is to simultaneously optimize for both. Second, our approach uses explicit counts to drive its explo- ration, which limits it to enumerable Mon-MDPs. Adapting psuedocount-basse methods (Bellemare et al., 2016; Martin et al., 2017: Tang et al., 2017; Machado et al., 2020) helps making Monitored MBIE-EB more applicable to large or continuous spaces. Finally, the decision of when to stop trying observe rewards and instead optimize essentially optimal stopping time problem (Lattimore & Szepesvári, 2020), and there are considerable innovations that could improve the bounds along with empirical performance.
however, it
To answer RQ4, now consider the performance of Known Monitor Figure 4d, showing the performance of Mon- itored MBIE-EB when provided the model of the Button Monitor 5% Results show that its convergence speed in- creases significantly, as Monitored MBIE-EB takes (on erage) 30% fewer steps to find the minimax-optimal policy. This feature of Monitored MBIE-EB is particularly impor- tant in settings where the agent has already learned about the monitor previously or the practitioner provides the agent with an accurate model of the monitor. The agent, then, needs only to learn about the environment, and does not need to explore the monitor component of the Mon-MDP.
To better understand the above results, Figure 5 shows how many times the agent visits the goal state and 1 states per testing episode. Both algorithms initially visit the goal state (Figure 5a) during random exploration (i.e., when executing the policy after 0 timesteps of training). Monitored MBIE- EB appropriately explores for some training episodes (recall that rewards only observed in ON and even then only 5% of the time), and then learns to always go to the goal. Both also initially visit 1 states (Figure 5b). However, while Monitored MBIE-EB learns to be appropriately pessimistic over time and avoids them, Directed-E2 never updates its (random) initial estimate of the value of 1 states and incor- rectly believes they should continue to be visited. This also
6. Conclusion
We introduced Monitored MBIE-EB for Mon-MDPs that addresses many of the previous work's shortcomings. It gives the first finite-time sample complexity for Mon-MDPs, while being applicable to both solvable and unsolvable Mon- MDPs, for which it is also the first. Furthermore, it both exploits the Mon-MDP's structure and leverage the monitor process's 's knowledge, available. These features are not just theoretical, as we see these innovations resulting in empiri- cal improvements in Mon-MDP benchmarks, outperforming the previous best learning algorithm.
by Parisi al. (2024a), pessimistic initialization with D results in asymptotic convergence for unsolvable Mon Mon-MDPs.
8

---

Model-Based Exploration in Mon-MDPs
Monitored MBIE-EB
Directed-E2
Minimax-Optimal
MDP
Semi-Random Random
Ask
Button
N-Supporters
Level Up
One: Hazard
River Swim
Corndo
Two Room-33 3x5
64
Two Two.Rooo Roc.RRom--20 2x11
Training Steps (x10²)
Figure 6: Performance on benchmark environments from Parisi et al. (2024a). Monitored MBIE-EB outperforms
Directed-E2 in 43 of them and performs on par in the remainder five. Details all 48 benchmarks are in Appendix B.
9

---

Model-Based Exploration in Mon-MDPs
Acknowledgments
Dixit, H. D., Pendharkar, S., Beadon, M., Mason, C., Chakravarthy, T., Muthiah, B., and Sankar, S. Silent data corruptions at scale. arXiv preprint arXiv:2102.11245, 2021.
The authors are grateful to Simone Parisi for helping in preparing this work, Antonie Bodley for enhancing the text's clarity, and the anonymous reviewers that provided valuable feedback. Part of this work has taken place in the Intelligent Robot Learning (IRL) Lab at the University of Alberta, which is supported in part by research grants from Alberta Innovates; Alberta Machine Intelligence Institute (Amii); a Canada CIFAR AI Chair, Amii; Digital Research Alliance of Canada; Mitacs; and the National Science and Engineering Research Council (NSERC).
Fiechter, C.-N. Efficient reinforcement learning. In Proceed- ings of the Seventh Annual Conference on Computational Learning Theory. Association for Computing Machinery, 1994.
Garivier, A. and Cappé, O. The KL-UCB algorithm for bounded stochastic bandits and beyond. In Proceedings of the 24th annual conference on learning theory, 2011.
Impact Statement
Hejna, J. and Sadigh, D. Inverse preference learning: Preference-based RL without reward function. Ad- vances in Neural Information Processing Systems, 2024.
This paper presents work whose goal is to advance the funda- mental understanding of reinforcement learning. Our work is mostly theoretical and experiments are conducted on sim- ple environments that do not involve human participants or concerning datasets, and it tied to specific real-world applications. We believe that our contribution has little to no potential for harmful impact.
Kaelbling, L. P., Littman, M. L., and Cassandra, A. R. Plan- ning and acting in partially observable stochastic domains. Artificial Intellgencee 1998.
Kakade, S. M. On the sample complexity of reinforcement learning. University of London, University College Lon- don (United Kingdom), 2003.
References
Kausik, C., Mutti, M., Pacchiano, A., and Tewari, A. A Framework for Partially Observed Neward-States, in RLHF arXiv preprint 2rXiv:2402.03282. 2024.
Andrychowicz, O. M., Baker, B., Chociej, M., Jozefowicz, R., McGrew, B., Pachocki, J., Petron, A.. Plappert, M., Powell, G., Ray, A., et al. Learning dexterous in-hand manipulation. The International Journal of Robotics Research, 2020.
Kearns, M. and Singh, S. Near-optimal reinforcement learn- ing in polynomial time. Machine learning, 2002.
Bartók, G., Foster, D. P., Pál, D., Rakhlin, A., and Szepesvári, C. Partial monitoring claitoring-cassificaatiin regret bounds, and algorithms. Mathematics of Operations Re- search, 2014.
Krueger, D., Leike, J., Evans, O., and Salvatier, Active Reinforcement Learning: Observing Rewards at Cost. arXiv:2011.06700 2020.
Lattimore, T. and Hutter, M. PAC bounds for discounted mdps. In Algorithmic Leurning Theory: 23rd Interna- tional Conference, ALT 2012, Lyon, France, October 29-31, 2012. Proceedings 23. Springer, 2012.
Bellemare, M., Srinivasan, S., Ostrovski, G., Schaul, T.,
Saxton, D., and Munos, R. Unifying count-based ex- ploration and intrinsic motivation. Advances in Neural Information Processing Systems, 2016.
Lattimore, T. and Szepesvári, C. Bandit algorithms. Cam- bridge University Press, 2020.
Bossev, D. P., Duncan, A. R., Gadlage, M. J., Roach, A. H.,, Kay, M. J., Szabo, C., Berger, J.J York, D. A., Williams, A., LaBel, K., et al. Radiation Failures in Intel 14nm Mi- croprocessors. In Military and Aerospace Programmable Logic Devices (MAPLD) Workshop, 2016.
Machado, M. C. and Bowling, M. Learning purposeful behaviour in the absence of rewards. arXiv preprint arXiv:1605.025 1605.07700, 2016.
Bowling, M., Martin, J. D., Abel, D., and Dabney, W. Set- tling the reward hypothesis. In International Conference on Machine Learning, 2023.
Machado, M. C.,, Bellemare, M. G., and Bowling, M. Count- based exploration with the successor representation. In Proceedings of the AAAI Conference on Artificial Intelli- gence, 2020.
Chadès, I., Pascal, L. V., Nicol, S., Fletcher, C. S., and Ferrer-Mestred J. A primer on partially observable Markov decision processes POMDPs. Methods Écol- ogy and Evolution, 2021.
Maillard, O.-A., Munos, R., and Stoltz, G. A finite-time analysis of multi-armed bandits problems with Kullback- Leibler divergences. In Proceedings of the 24th annual Conference On Learning Theory, 2011.
10

---

Model-Based Exploration in Mon-MDPs
Mannor, S. and Tsitsiklis, J. N. The Sample Complexity of Exploration in the Multi-Armed Bandit Problem. J. Mach. Learn. Res., 2004.
Schulze, S. and Evans, O. Active Reinforcement Learning with Monte-Carlo Tree Search, arXiv: (xXiv:/03300492/ 2018.
Shao, L., Migimatsu, T., Zhang. Q. Yang. K., and Bohg, J. Concept2Robot: Learning manipulation concepts from in- structions and human demonstrations. The International Journal of Robotics Research, 2020.
Martin, J., Sasikumar, S. N., Everitt, T., and Hutter, M. Count-based exploration in feature space for reinforce- ment learning. arXiv preprint vtXiv:/76.008090 2017.
Osband, I,, Roy, B. V., Russo, D. J., and Wen, Z. Deep Exploration via Randomized Value Functions. Journal of Machine Learning Research, 2019.
Strehl, A. L. and Littman, M. L. An analysis of model- based interval estimation for Markov decision processes. Journal of Computer and System Sciences (JCSS), 2008.
Parisi, S., Kazemipour, A., and Bowling, M. Beyond Opti- mism: Exploration With Partially Observable Rewards. In Advances in Neural Information Processing Systems, 2024a.
Strehl, A. L., Li, L., and Littman, M. L. Reinforcement Learning in Finite MDPs: PAC Analysis. Journal of Machine Learning Research, 2009.
Sutton, R. S. and Barto, A. G. Reinforcement Learning: An Introduction. MIT Press, 2018.
Parisi, S., Mohammedalamen, M., Kazemipour, A.. Taylor, M. E., and Bowling, M. Monitored Markov Decision Processes. International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2024b.
Szita, I. and Szepesvári, C. Model-based reinforcement learning with nearly tight exploration complexity bounds. In Proceedings of the 27th International Conference on International Conference on Machine Learning, 2010.
Pilarski, P. M., Dawson, M. R., Degris, T., Fahimi, F., Carey, J. P., and Sutton, R. S. Online human training of my- oelectric prosthesis controller via actor-critic reinforce- ment learning. In 2011 IEEE International Conference on Rehabilitation Robotics, 2011.
Tang, H., Houthooft, R., Foote, D., Stooke, A., Xi Chen, O.,
Duan, Y., Schulman, J., DeTurck, F., and Abbeel, P. Exploration: A study of count-based exploration for deep reinforcement learning. Advances in Neural Information Processing Systems, 2017.
Puterman, M. L.. Discounted Markov Decision Problems. Markov Decision Processes. John Wiley & Sons, Ltd. pp. 142-276 1994.
Vu, T. L., Mukherjee, S., Huang, R., and Huang, Q. Barrier Function based Safe Reinforcement Learning for Emer- gency Control of Power Systems. In 2021 60th IEEE Conference on Decision and Control (CDC), 2021.
Regan, K. and Boutilier, C. Robust Policy Computation in Uncertann MDPs Using Nondominated Poli- cies. Proceedings of the AAAI Conference on Artificial Intelligence, 2010.

---

Model-Based Exploration in Mon-MDPs
In this appendix we provide the proof of the sample complexity bound of Monitored MBIE-EB, the description of how the set of indistinguishable Mon-MDP [M] for truthful Mon-MDP is defined, the proof of the tightness of the Monitored MBIE-EB's s sample complexity on p=1 additional details about Monitored MBIE-EB and its pseudocode, the details of experiments (including description of the environments and monitors, details of the hyperparameters, an outline of Directed-H², and left-out implementation details), and ablations on the significant components of Monitored MBIE-EB.
A. Table of Notation
Symbol
Explanation
A(X)
( denotes the set of distributions over the finite set
M
Mon-MDP
The probability measure
The expectation with respect to IP
S
State space (environment-only in MDPs, joint environmentt-montoor in Mon-MDPs)
A
Action space (environment-only in MDPs, joint cottmmmett-moniion in Mon-MDPs)
r(s,a)
Mean reward of taking action at state s Transition dynamics MDPs / Joint transition dynamics in Mon-MDPs Maximum likelihood estimate of Optimistic variant of p
P
P
P
y
Discount factor
re
Maximum mean environment reward
max
e
Tiux
Se
Environment state space
A
Environment action space
RG
Immediate environment reward for timestep &
T
Immediate environment proxy reward for timestep Maximum likelihood estimate of r
Re
Re
Optimistic variant of r Environment transition dynamics Monitor state space
yf
S
ym
Monitor transition dynamics
fm
Monitor function
am
Maximum expected monitor reward mmx
max
m
min
N(s a)
Number of times a has been taken at s
N(s an)
Number of times a has been taken at Number of times a has been taken s and the environment reward observed
Ns a
Number of observe episodes
x² (k)
Desired number of observe episodes through episode k
The minimum non-zero probability of observing the environment reward
B. Methodological Details and Results
Throughout the paper, our baseline is Directed-E" as the precursor of our work. Parisi et al. (2024a) showed the superior Directed-E's "rected-E''s performance in Mon-MDPs against many well-established algorithms. Directed-E' uses two action values, one as the ordinary action-values that uses a reward model in place the environment reward to update task-respecting action-values (this sets the agent free from the partial observability of the environment reward once the reward model learned). The Second action-value denoted by V, dubbed as visitation-values tries to maximize the successor representations. Directed-E2 uses visitation-valuu comparable range. In the limit of infinite exploration, Directed-E2 becomes greedy with respect the task-respecting action-values for maximizing the expected sum of discounted rewards.
visit every joint state-action pairs and it tries maintain the visitation of each pair in
Evaluation is based on discounted test return, averaged over 30 seeds with 95% confidence intervals. Every 100 steps, learning is paused, the agent is tested for 100 episodes, and the mean return recorded
12

---

Model-Based Exploration in Mon-MDPs
Empty
Hazard
Bottleneck
T
Two-Room-2x11
River Swim
Loop
Corridor
One-Way
Two-Room-3x5
OIE TOOP
OUr mcr
Dise DAY
ANIA 3ND
ONE WAY
OHE WAY
QUE WAY
CINE WAY
Figure 7: Full set of environments. Except Bottleneck, all environments are borrowed from Parisi et al. (2024a). Snakes and Wasps should be avoided. The goal is to STAY at the treasure chest. Gold bars are distractors. The agent gets stuck in the holes unless randomly gets pulled out. One-ways transition the agent in their own direction regardless the action.
B.1. Full Environments' Details
and 1vo-Room-2x11. They are shown in Figure 7. In all of them (except River Swim) the agent, represented by the robot, has 5 actions including 4 cardinal movement {LEFT, DOWN, RIGHT, JP} and an extra STAY action. The goal is getting to the treasure chest as fast as possible and STAYing there to get reward of +1, which also terminates the episode. The agent should not STAY at gold bars as they are distractors because they would yield a reward of and terminate The agent should avoid Snakes as any action leading them yield reward of -10. Cells with one-way sign transition the agent only their unique direction. If the agent stumbles hole, it would spend the whole episode in it, unless with 10% chance its action gets to be effective and the agent gets transitioned. When button monitor is configured environment, the location of the button is figuratively indicated by push button. The button is pushed if the agent bumps itself to it. The episode's time limit in River Swim, corridor and Two-Room-2x11 is 200 steps, and in other environments is 50 steps. In River Swim the agent has two actions L = LEFT and R = RIGHT, and there is no termination except the episode's time limit. In this environment gold bars have a reward of 0.01. Figure 8 shows the dynamics of River Swim.
The environments comprise Empty, Hazard, Bottleneck, Loop, River Swim, One- May,Way, Corridor,
episode.
top of the
B.2. Full Monitors' Details
Monitors used in the experiments are: Full (MDP), Semi-Random, Full-Random, Ask, Button, N-Supporters, N- Experts and Level-Up. For any of the monitors, except Full-Monitor, a cell in the environment is marked with L., then under no cireumstances and no timestep, the monitor would reveal the environment reward agent for the action that led
13

---

Model-Based Exploration in Mon-MDPs
(R. 0.4, 0)
(R. 0.8,
(R. 0.8, 0)
(R. 0.8, 0)
(R. 0.6, 0)
[R. 0.6,
1,,1,
0
(R. 0.6, 0)
(R. 0.35, 0)
2
(R. 0.35, 0)
3
(R. 0.35, 0)
4
(R. 0.35, 0)
5
(L, 1,
1L,10) (R, 0.050.5.00
(L. 1,
1L,
(L, (R, 0.4, 0)
(R. 0.05, 0)
(R, 0.05, 0)
0.05, 0)
Figure 8: Dynamics of River Swim. Each tuple represents (action, transition probability, reward).
the agent to that cell. For the rest of the environment state-action pairs the behavior of monitors at timestep 2 0, by letting X₂ ~ U(0, I], where U is the uniform distribution and E [0, Il, is as follows:
Full. This corresponds the MDP setting. Monitor shows the environment reward for all environment state-action pairs. State space and action state space of the monitor are singletons and the monitor reward is zero:
Sth = {ON},
ATh
S = ON,
1 4+1 = 0,
16+11
Semi- Semi-Random. It is similar to Full- Mull-Monitor except that non-zero environment rewards get hidden with 50% chance:
R2
if R 1+1 0;
STD = {ON},
ATh = (NO-OP},
S == ON,
Rm ++
= O.
RS = Ri+1
else if X, < 0.5 Otherwise.
Ranl-R. is similar to except any environment reward gets hidden with predefined chance p.
R
if X, S
STh = {ON),
ATh (NO-OP}.
Sm
ON,
R
O,
1
Otherwise.
Ask. The monitor state space is singleton but its action space has two elements: {ASK, NO-OP). The agent gets the environment reward with probability p if it ASKs. Upon ASKing the agent pays -0.2 as the monitor reward:
8Th = {ON},
ATh = {ASK, NO-OP),
1+1 == ON,
R
if X, S p and AT = ASK: Otherwise;
-
0.2,
if AT = =SK;
RC
R441
0,
Otherwise.
Button. The state space is (ON, OFF}. The action space is a singleton. The agent sees the environment reward with probability p as long as the monitor is ON, while paying -0.2. The state is flipped if the agent bumps itself to the button:
RC
R if X, S p and S. ON;
Sm = {OFF, O
AATh = [NO-OP},
R
Otherwise;
ON,
if STh OFF and S "BUTTON-CELL" and A "BUMP-INTO-BUTION""
Sm
OFF,
if 5Thh = ON and S BOUTTON-CELLE and A INMP-INNTOBUUTTON BUTTON"; Otherwise;
S
0.2, if S ON; Otherwise.
S0 Random uniform from Sm
R ==
0,
The monitor state space comprises N states that each represents the presence of supporter. The action space also comprises N actions. At each timestep one of the supporters is randomly present and if the agent could
N-Supporters.
14

---

Model-Based Exploration in Mon-MDPs
choose the action that matches the index of the present supporter, then the agent gets see the environment reward with probability p. Upon observing the environment reward agent pays penalty of -0.2 as the monitor reward. However, if the agent chooses wrong supporter, then it will be rewarded 0.001 (as distraction) the monitor reward:
TTh = =0, (..... ,N 17,
{0, ,N 1), A
S41
Random uniform from Smh,
Ri+1: if X S and STD
Ap
-.22
=
= Am,
R
R 0.001, Otherwise.
Otherwise;
Parisi et al. (2024a) considered this monitor challenging, due to its bigger spaces than the rest of the monitors, for algorithms that use the successor representations for exploration. However, the encouraging nature of the monitor regarding the agent's 's mistakes makes the monitor easy for rewaardrespecttngg algorithmss, c.g. Monitored MBIE-EB.
N-Experts. Similar to N-Supporter the state space has N states, each corresponding to the presence of one of the N experts. However, getting experts" advice is costly, hence the action space has N + action where the last action corresponds to not pinging any experts and is cost-free. At each timestep, one of the experts is randomly present and if the agent selects the action that matches the present expert's index, the agent gets to see the environment reward with probability p. Upon observing the environment reward agent pays a penalty of -0.2 as the monitor reward. However, if the agent chooses a wrong expert it will be penalized by -0.001 as the monitor reward. Since the last action does not inquire any of the experts its monitor reward is O:
8th = (0, -0, ... N 1},
ATh = ,O,..., ,N,,
S41
Random uniform from Sm
0.2,
if S.h = AA;
Ri-1: L.
if S p and StD AT
R1
R 0,
else if AT = N; Otherwise.
Otherwise;
-0.001,
Level-Up. This monitor tries to test the agent's capabilities of performing deep exploration (Osband et al., 2019) in the monitor spaces. The state space has N states corresponding to N levels. The action space has N + actions. The initial state of the monitor is 0 and if at each timestep the agent selects the action that matches the state of the monitor, the state increases by one. If the agent selects the wrong action the state is reset back to O. The agent only gets to observe the environment reward with probability p if it gets the state of the monitor to the max level. The agent is penalized with -0.2 as the monitor reward every time it does not select the last action which does nothing and keeps the state as is:
R
if S p and ST = - 1;
8th = {0, ... N - 1}.
ATh = 10..... .N- - L,NO-OP,,
Ri41
1,
Otherwise;
Sm
AT OP;
0, if AT = NO-OP;
RT41 =
St1 =
max S + +1,N - 1).
else if ST AT;
-0.2, Otherwise;
0,
Otherwise.
B.3. When There Are Never-Observable Rewards
Mon-MDPs designed by Parisi et al. (2024a) do not have non-ergodic monitors, which give rise to unsolvable Mon-MDPs. Hence, we introduce Bottleneck to investigate the performance of Monitored MBIE-EB compared to Directed-E2 in unsolvable Mon-MDPs. In Bottleneck the underlying reward of cells marked by 1. is the same as the snake (-10). In these experiments, we use Full-Random monitor since is more stochastic than are shown Figure 9. The location the button is chosen to make agents perform deep exploration because changing the state of the button requires long sequence of costly actions, which in turn yields the highest return. Therefore, the range of returns obtained with Button monitor is naturally lower than the rest of the Mon-MDPs.
Random to increase the difficulty. Results
As noted in Footnote 9, Directed-EE's performance in unsolvable Mon-MDPs depends critically on its reward model initialization. In order to see minimax-optimal performance from that algorithm, we need to initialize it pessimistically. As shown in Figures 4b and 4c, using the recommended random initialization saw essentially no learning in these domains. The algorithm would believe the never-observable rewards were at their initialized value, and so seek them out rather than treat their value pessimistically. Also, one of the weaknesses of Directed-E' is its explicit dependence on the size of the
15

---

Model-Based Exploration in Mon-MDPs
state-action space during its exploration phase, i.e., Directed-EA tries visit every joint state-action pair infinitely often without paying attention their importance on maximizing the return. As result, as the state-action space gets larger, the performance of Directed-E' deteriorates. To highlight the Directed-E2's weakness in larger spaces, use N-Experts monitor as an extension of Ask monitor, Ask is the special case when N = 1. Figure 9 shows Directed-E"t performance is hindered when the agent faces N-Experts compared to Ask, while Monitored MBIE-EB suffers to lesser degree.
Monitored MBIE-EB
Directed-E
Minimax-Optimal
Rallomandm
Ask
N N-puprrrters
E-Expests
Level Up
Botslenock
Training Steps (x10²)
Figure 9: Monitored MBIE-EB outperforms Directed-E on Bottleneck with a non-ergodic monitor. Even though Directed-B2's reward model initialized pessimistically achieve asymptotic minimax-optimality its dependence the state and action spaces' size makes it struggle more than Monitored MBIE-EB on N N-Suppooters, N N-Experts and Level Up.
B.4. When There Are
Rewards
In all the previous experiments, had agent done the action that would have revealed the environment reward, e.g., ASKing in Ask monitor, by paying the cost it would have observed the reward with 100% certainty. But, even if the probability is not 100% and yet bigger than zero, upon enough attempts to observe the reward and paying the cost, even if a portion of the attemps are fruitless, it is still possible to observe and learn the environment mean reward. In the Figure 10's experiments, in addition to have environment state-action pairs that their reward is permanently unobservable, stochastic for other pairs, i.e., if the agent pays the cost, it would only observe the reward only with probability p. Figure 10 illustrates that albeit the challenge of having stochastically and also permanently unobservable rewards, Monitored MBIE-EB has not become prematurely pessimistic about the rewards that can be effectively observed, even when the probability goes down as low as 5%, and still Monitored MBIE-EB outperforms Directed-E2.
make the monitor
Monitored MBIE-EB
Directed-E2
Minimax-Optimal
Full-Random
Ask
N Suppprrtes
N-Experts
Level Up
Button
(80%)
-22
2.5
(20%)
(5%))
Training Steps (x10²)
Figure 10: Monitored MBIE-EB outperforms Directed-E2 on Bottleneck even if environment rewards are stochasti- cally observable. The plots empirically show the effect of p in the Monitored MBIE-EBI sample complexity stated in Theorem 3.1. For fixed environment and monitor, as the probability of observing the reward decreases, more samples are required to find minimax-optimal policy. The plots also indicates that although the sample complexity of Directed-E' has never been given theoretically, but it must more severely depend p than Monitored MBIE-EB's
16

---

Model-Based Exploration in Mon-MDPs
B.5. When The Monitor is Known
In this section, we verify knowing the monitor speeds up the Monitored MBIE-EB's learning. We empirically demonstrate knowing the monitor is advantage Monitored MBIE-EB benefit from, while it is not readily possible in model-free algorithm such Directed-E². So far, we have shown the superior performance of Monitored MBIE-EB against Directed-E', now we investigate how much of the learning's difficulty in Mon-MDPs comes from the monitor being unknown, The unknown quantities of the monitor are ,"",p" and fm hence in the Figure 1l's experiments we make all of them known to the agent in advance. The only remaining unknowns are re and p². Hence, we replace Equation (8) with
B/ g(N((s))) (s 10.s,,05 a²)
Roba (s, a) = (Ret( * -.s A, =
where (s , d)) counts the number of times 8 a has been visited, No(5 = En (8 ,a") and is defined in Footnote 7.
(x)) The intuition behind the bonus By No is that p 1f @ yd and we only need to account for the uncertainty stemming from knowing pº. Note since the monitor is known there no need to use KL-UCB, as the agent already knows which environment rewards are observable (with what probability) and which ones not. Similarly, replace Equation (5) with
(N((s)) ((se, as)
9 (N,((s))
(8, (8),a)) 80
(s" + B
(s a²)²
where the bonus g0 gets more accurate by visiting insufficiently visited environment state-actions. Figure 11 shows the prior knowledge the
)()) ((
is due to the environment mean reward, and B
((N)( (= accounts for the fact that pe only
monitor boosts the speed of Monitored MBIE-EB's learning and make it robust even in the low probability regimes.
Monitored MBIE EB
DirectediE
Known Monitor
Minimax Optimal
Full-Random
Ask
#-Supporters
N-Experts
Level Up
Button
8.
(80%)
-22
0.1
2006
-12-
(969
Training Steps (x10*)
Figure 11: Knowing the monitoring process considerably accelerates learning in Mon-MDPs. The similar learning speed in Ask and N N-Experts show that the knowledge of the monitor make Monitored MBIE-EB robust against the size of the monitor spaces. Also, the similarity of learning speed for fixed environment and monitor across experiments with high and low observability chance shows that the given knowledge of the monitor help the agent foeus its exploration state-actions that their environment rewards is observable even if the probability is low.
C. Ablation Studies
In this section, we show that our innovations are crucial to extend MBIE-EB to Mon-MDPs. We show that without all our proposed innovations, there exists at least one setting that the resulting algorithm without the full innovations fails.
17

---

Model-Based Exploration in Mon-MDPs
Monitored MBIE-EB
Optimistic MBIE-EB
Minimax-Optimal
Full-Random
Ask
N Supporters
N Experts
Level Up
Bottleneck
-0.
Training Steps (x10²)
(a) Comparison between Monitored MBIE-EB and MBIE-EB solvable Bottleneck. When all the rewards are observable, MBIE-
EB's 's optimism is effective to learn all the unknown quantities. MBIE-EB matches the performance of Monitored MBIE-EB.
Full- Full-Random
Ask
Supporters
ExExrrts
Button
(100%)
Training Steps (x10
(b) Comparison between Monitored MBIE-EB and MBIE-EB in unsolvable Bottleneck. While Monitored MBIE-EB is pessimistic with respect to unobservable rewards, MBIE-EB remains mistakenly optimistic. MBIE-EB's optimism leads to endless visits to 1 cells,
Figure 12: Verityingg the importance of the second innovation: pessimism instead of optimism.
Monitored MBIE-EB EB
Pessimistic MBIE-EB
Minimax-Optimal
Rall-Random
Ask
Supporters
N Experts
Level Up
Button
Bottleneck
0.2
-15
0.2
Training Steps (x10²)
(a) Comparison between Monitored MBIE-EB and pessimistic MBIE-EB in solvable Bottleneck. When all the rewards are
deterministically observahle, pessimistic MBIE-EB is effective hecause single visit every state-action is sufficient to conclude that the reward is observable. Therefore, pessimistic MBIE-EB matches the performance of Monitored MBIE-EB.
Full-Random
Ask
N Supporrters
N ExExperts
Level Up
Button
(100%)
-32
-25
(986)
-2.0
Training Steps (x10²)
(b) Comparison between Monitored MBIE-EB and pessimistic MBIE-EB in unsolvable Bottleneck. With deterministic observability, pessimistic MBIE-EB effective in finding the minimax-optimalii
But with stochastic ohservability, pessimistic MBIE-EB due premature pessimism with respect to state-actions that their reward can be observed upon enough exploration fails. On the other hand, due to exploring to observe the reward, Monitored MBIE-ED EB is robust against the stochasticity in the observability of the rewards.
Figure 13: Verifying the importance of the third innovation: explore to observe rewards.
C.1. Importance of the Second Innovation: Pessimism Instead of Optimism
MBIE-EB uses the optimistic initial action- values for acttenactions that their counts are zero. That is, in Mon-MDPs for any joint state-action pairs (s, a) = sm amm.a a²,
a) that any of (s* a²), N (s am),, , or N(s, a) is zero, Q(s, a) would
18

---

Model-Based Exploration in Mon-MDPs
be shortcut an optimistic value. This approach contrasts with the Equation (6)'s pessimism, when N(s, a²) is zero. Therefore, first we show that on Bottleneck environment, when the reward of all I. cells is observable, MBIE-EB is effective because upon enough visitation resulting from the optimism, the underlying environment reward will finally be observed. Figure 12a shows the MBIE-EB 's efficacy in solvable Mon-MDP: However, we then show the lack of necessary pessimism when the reward of all I. cells is unobservable make MBIE-EB ineffective. The MBIE-EB's inefficacy in unsolvable Mon-MDPs due to the fact that the optimism never decreases, hence the agent would continue visiting state-actions with unobservable rewards for ever. Figure 12b shows the MBIE-EB's failure in the unsolvable Bottleneck.
C.2. Importance of the Third Innovation: Explore to Observe Rewards.
Appendix C.1 showed the excessive optimism of MBIE-EB hinders its performance in unsolvable Mon-MDPs, Now, we demonstrate without exploring to observe rewards, using pessimism alone still prone to failure. We extend MBIE-EB to Mon-MDPs and for all state-actions (s, a) =s", s sm "m" a,",, when (s", a²) zero, we use " This approach effective in Mon-MDPs with deterministic observability (p 1). Figure 1 13 shows the efficacy of pessimistic MBIE-EB in solvable Bottleneck with deterministic observability. Pessimistic MBIE-EB is also effective in unsolvable Mon-MDPs with deterministic observability, where only one visit to each state- action concludes whether the environment reward is observable or not. Figure 13b, (100%) row verifies this claim for pessimistic MBIE-EB on unsolvable Bottleneck with 100% observability. However, if the observability is stochastic then premature pessimism hinders the pessimistic MBIE-EB's performance because the algorithm has become pessimistic with respect to state-actions that otherwise could have observed their rewards eventually. This shortcoming of the pessimistic MBIE-EB compared Monitored MBIE-EB that explore to observe the rewards and then uses pessimism with high confidence is evident in Figure 13b, (5%) row.
D. Pseudocode
Algorithm Monitored MBIE-
Require: Qope-intss Qota-init
1: @ 0
2: 6 +0
3: for episodes = 1,2,3.... do
4: if S x² (k:) then
5:
// Observe Episode
6:
Compute Qona by performing 50 steps of value iteration on Equation (8), or use Qohe-init if counts are zero.
7:
Q+ Qate
8:
x
# K +1
9:
else
// Optimize Episode
11:
Compute Qopt by performing 50 steps of value iteration on Equation (6), use Qpp--int if counts are zero.
12:
Q + Qopt
13:
end if
14:
for steps h 1,2,... ... do
15:
Follow the greedy policy with respect to Q
16: end for
17:
end for
E. Low-Level Implementation Specifics
The minimum non-zero probability of observing the reward p is by default one unless otherwise states. In experiments that include N N-Supporters N-Experts, N is equal to four, and the number of levels for Level-Up is three. Hyperparameters of Directed-FE2 consist of: Qim the initial action-values, Vo the initial visitation-valle values,, the initial values of the environment reward model, 3 goal-conditioned threshold specifying when joint state-action pair should be visited using visitation-values a the learning rate to update each Q or 5 incrementally, and discount factor 7 that is held fixed to 0.99. These values are directly reported from Parisi et al. (2024a). Monitored MBIE-EB' B hyperparameters are set per environment and do not change across monitors. The same applies to Directed-E22 but Parisi et (2024a) recommended to anneal the learning rate
19

---

Model-Based Exploration in Mon-MDPs
Algorithm/ 2 Directed-E"
Require: Qints iitt Q < Qini. +- V in
2: 2- // Total timesteps
3: for episodes k == 1, 1,2,... do
4: for steps h = 1, ... do
5:
(s$,a=) &- arg min,,a ((,
6: 3. -- (d)
7:
if 3 > then An +- arg max, (a Sh. ,8,a8) (8)/ // Explore
8:
else A < arg max, (Sn. a) // Exploit
9:
:= 1
10: Perform action A
11: end for
12:
end for
for N N-Supporters and N Expertss. KL-UCB has no closed form solution. We computed it using the Newton's method. The stopping condition for the Newton's method was chosen 50 iterations or the accuracy of at least 10-5 between successive solutions, which one happened first. We ran all the experiments on a SLURM-baser cluster, using 32 Intel E5-2683 v4 Broadwell @ 2. 1GHz CPUs. Thirty parallel runs took about an hour on a 32 core CPU.
E.1. Hyperparameters
Let denote the uniform distribution and x + y the linear annealing from æ to y. Table lists the hyperparameters used.
Table I:
The set of hyperparameters.
(a) Hyperparameters of Monitored MBIE-EB across experiments.
Unknown monitor
Experiment
Environment
Qept-init
Qabs-init
x² (k)
3KL-UCB
gobs |,, 3 /
Empty
1
100
log1.005
5 X 10-2
5 X 10 4
Hazard
1
100
10g1.005 A:
5 x 10-2
5 x 10-4
Figure 6
One-Way
1
100
log1.00s A
5 x 10-2
5 x 10-4
River-Swim
30
100
log 005 At
5 x 10-2
5 x 10-4
Appendix B.3
Bottleneck
1
100
log 005
5 x 10-2
5 x 10-4
Appendix B.4
Bottleneck
100
logi.0os
5 x 10-2
5 x 10
Known monitor
Experiment
Environment
Qopt-init
Qobs-init
Kyt (k)
g
Appendix B.5
Bottleneck
100
log1 005
x 10-1
10
(b) Hyperparameters of MBIE-EB across experiments.
Experiment
Environment
Qupt-init
8, 1,.mm,.8 3
Appendix C
Bottleneck
50
10 1
(c) Hyperparameters of Directed-E' E² across experiments.
(Amnealing for N-Supporters and N --xperts)
Experiment
Environment
Qin
Vin
To
B
Empty
u|-0.1,0.1
10-2
(1++0 0.1)
One-Way
-10
4[[0.110.1
10-2
1(1++0.1)
Figure
Hazard
-10
4[-0.1,0.11
10-2
0.1))
River-Swim
-10
4[-0.1,0.1
10-2
0.5
Appendix B.4
Bottleneck
-10
-10
10-
1(1
Appendix B.4
Bottleneck
-0
-10
10-2
1(1
20

---

Therefore, = In convex. Also by Model-Based Exploration in Mon-MDPs
F. Auxiliary Propositions
Lemma F.1. For any a, x > 0, x 2 2a In implies x 2 a In æ.
Proof. First we prove that for Væ > 0: x x. Consider the function = I always true its domain. we have that
In æ. is enough to prove that y >
dy
Ly
2 x²
> 0.
dr x
dx
dy
2
=0 I
dx
I
the minimum of y 2 In 2-2 0. Thus, x 211 Vx >
Back to the inequalities in the lemma, let
then need to prove that 2 2 2n implies 2 2 In (2.
If a 2 2, then
In a2) = In + la I 2lna S 2.
Which is by the assumption of = 2 a
If a < 2, then
l < luz + In (z- a) < 2n < 2. which is by our proof in the beginning, where we showed 2 21 2, Vz > 0.
Lemma F22. Let S2 be an outcome space, and each of ( (Xi) and (Y:)== be n random variables on Q. holds that:
(
Σ X1 2 Σ Y1 c
Proof. Proof by contradiction.
Suppose (Ein X; Ei= Yi) (U (X: Y.),, then there exists an E Z that E Xi(w) > Σm Y((w) but
(w) (2), < Y2( (n((w) < (w) resulting in E Xi(w) < E Y((w) which is contradiction.
Corollary F3. Let (Xi) and (Yi) be random variables probability space (D,F,)) It holds that:
P
Σ
X
Σ
Yi
P (X,
1=1
Proof. Using Lemma F.2 and due to monotonicity of measures we have
(U(x22))
Σ x Σ Y
SP
By applying the union bound the inequality is obtained.
Lemma F4. Let M1 = AS,A, P1, fm" .7) and M2 = (S, A, r2, P2, fm be two Mon-MDPs. Assume that
- S <ri < m and
m < I TT, S r
Additionally assume that for all joint state-action pairs (s, a) = (8" 8h, "d,aa")) it holds that |rf("", ,a") - - S ":
[x" aa") ( )( S ym,
|p (8,8) pel 18, s.
Then for any stationary deterministic policies n, it holds that
- - (s, 4" + nr + (1
mar
r
max
(1 7)2
21

---

Model-Based Exploration in Mon-MDPs
Proof. Let
A = max (8 (s(.
A -==))( - (2(6
="=rT(c _a"') - -r2 (s "="""aa0 aa");
(s,a)
AP
Σ (s - Σ (s' 1/2 (5).
Then
+ I
(Triangle inequality)
60 + pThh +
Σ 6) (s')
p5)
40 + pm + 7
V2 (6')) E (4(6115a)VV(()mmmm6111 (8) p6 ())
x0 + p + 7
Σ (VE (1 (s'))
(s'1s,
$ <500 + pm + 7
Σ pi ( (6)) V3 (6))
+ Σ -
-2) 1/ (5)
2730 (riux + max
S 0 + m +
Σ pi (s'ls, (VF (6) V5 (6))
+
By taking the (a.)) from the both sides we have
274 (rinxx + mmxx
A < 00 + t 7
1 1-7 y
(1 A) I 8e + pm + 27p (rim.x + m'xx)
1 1-
6 + 4m
+ 2yp (r + rmax
60 + 40th + 2r max rum max
(1 -1-99 7)
(1 7)²
Since (Q] a) (s, a)l S A, the proof is completed.
Lemma F.5. Let Mi = AS,A, A, r1, 1m 7) and M2 = (S, A. 12, p2, (',,)) be two Mon-MDPs. Assume that:
- S $ Srr m
and
m S STT, S m
Suppose further that for all joint state-action pairs (8,a) = (6f, "0,,"",a" ",,,,"" an),, holds Irs(s, .f) rg d S (s"h, a"") - (s" d")) S 6m
[pI(- ((,1),a)= ( -p2(- ss p.
(oa traw), 1-y and any stationary policy n, if 10th x = C E(112))
There exists a constant C' that for any 0 SeS
rau tra then
(8, (s, Se
Proof. Using Lemma F.4, show that 3 5" 22pr(r 24p (1-7)²
+ tr (1-7)a
5(1 ((1->)
which yields ip -
2(+7 +
By assumption that ffax = rmxx and choosing C' = we have
s(1-3)²
e(1-7)²
6
2(147(r
Lemma F.6 (Chernoff- (Cheroof-Hoeffdding' 's inequality). For (X,) independent identically distributed samples on probability space F,P), where X; E [o,, for all and e 0, we have
2n²2 S exx
P
E
Σ 1=1
X 2
--= (b; 0,)2
22

---

Model-Based Exploration in Mon-MDPs
G. Proof of Theorem 3.1
The complete proof essentially follows all the steps of Strehl & Littman (2008, Theorem 2) with additional modifications. We only provide proofs for components that are non-trivially distinct between MDPs and Mon-MDPs when the analysis of Strehl & Littman (2008, Theorem 2) is applied. Essentially, Theorem 3.1 comprises five high probability statements:
1. Specifying the number of samples required estimate the observability of the environment reward in observe episodes
2. Optimism of Qois
3. Specifying the number of samples required to find a near minimax-optimal policy in optimize episodes
4. Optimism of Qopt
5. Determining the sample complexity
For the first steps of the proof let
bs, a) = [ ( # 13. (N(S,, 49) = 0) = 8, A, =
denote the expected observability of the environment reward for a joint state-action (s, a) that its environment reward has not been observed until timestep t. Note that the KL-UCB term in Equation (8) is an upper confidence bound on b. Also, define B to be the maximum likelihood estimation of b.
G.1. Specifying The Number of Samples Required to Estimate The Observability of Reward in Observe Episodes
According to Strehl & Littman (2008, Lemma 2), to find policy in observe episodes that its action-values, computed using B and P, are E1-accurate, B and P should be 7-close to their true mean for all state-actions (s, a), where T = (1 Hence, to specify the least number of visits m, to (s, a) to fulfill the r-closeness, we must have
P( a) p(- s, a)) S r,
(10)
[Bss a) b(s, a) 5.
(11)
Also, according Strehl & Littman (2008) if (s, a) has been visited my times, with probabilities least 1 82 and 85.
2 In (2|S) 2) In sp]
In go 2m1
|| P( 8, - p(- ss ssaa)) s
B(s, a) - b(s a)) S
m1
Hence, for Equations (10) and (11) to hold simultaneously with probability - 6, until (s.a) a) is visited m, times, by setting 8 8hh
s Al my to split the failure probability equally for all state-actions until each of them has been visited my times, it is enough to ensure 7 is bigger than the length of the confidence intervals:
8 In (2|5)
2) - In 50
21n
2
8 In (2
2) In 23 2
In
1 1|8|LAm
g6
81
mi max
max
72
72
72
8 In (2|s) 2) + In 2| mi
B1
(12)
72
Lemma F.1 helps us to bring my out of the right-hand side of Equation (12). Hence,
mi = o | +
1 = = Is
S Tō,
1
1S| |A|
(13)
-1-1-)1 71117)* 61 (1 -
Equation (13) shows the fact that regardless of how infinitesimal the probability of observing the reward is, in the worst-case the difficulty of learning expected observability lies in learning the transition dynamics (Kakade, 2003; Szita & Szepesvári, 2010), i.., by the time the transition dynamics are approximately learned, the agent has approximately figured out what the probability of observing the environment reward for taking any joint action is.
23

---

Model-Based Exploration in Mon-MDPs
G.2. Optimism of Qohs
Optimism is needed make sure the agent has enough incentives visit state-actions with inaccurate statisties. Suppose my is the least number of samples required to ensure B and P are accurate. Therefore, the agent should be optimistic about the state-actions that have not been visited my times yet. Let
Vaha (s, a) = b(s, + Σ p(s' | 8, a) max (2h (s',a').
Now consider the first visits to (s, a) during observe episodes, where my and consider Qoos
(sna =) B(s, a) + P(s' P(s' 8, a) max Qoos d') + gubs
(14)
a²
Vi
But, B(s,a) a) is zero for all state-action pairs. Because if B(s, a) is not zero, then (N(S), A2) 0|S, = A, a} must return one, which means environment reward of (s, a) has not been observed until timestep t. Consequently,
Rr # 1 S s, A: a) has been zero until timestep t. Therefore, Equation (14) turns into
Qoos(s, ? Σ P(s' 88 max Dora 25 (8','') a') + gohc
(15)
Ve
According to Strehl & Littman (2008, Lemma 7), by choosing gohs (1 (1-7)-1 V 0.5
[4sS|[A|m b1
P(s' s,a) max Poos (s', d') + gobs Vv
(s)
= ()
2 (s, a),
a'
with probability at least
h On the other hand by choosing BKL.UCB = 1nn444111 [|| [A| m1d1),
A|mm
gKI.UCB
KL-UCB (v)
max/ue [0, 1] d(0, 1)
ž b(s,a),
with probability at least
6
Now define the random variables X1 and X2 as
4.S|A Almi
X1 Qito (s, 7 Σ P(s') s, s, max (s',a'
X2 B(s, a) 0.
We have:
gobs
81 4 [|| Am
P X 2 max l E [0, d(0, 1) S BKL-UCB
52
P
X1
SSS |A|
m1
Using Corollary F.3 we have:
81
(X + X Y1 X2) S
2|S |A| m
Therefore, with probability least
2|5 [|mm we must have that Xi + X2 5 Yi Y2. Thus,
(s, - Σ P(s' s, max Qona (5', a') Y - Yy2
5¹
(s, 5 P(s') 8, ma max Q (s',a') + +Y - Y2
(s) < (s) + max { 4 10, :(0))d(00.)) <
3KL.UCB
By abusing the notation for Qats to incorporate the KL-UCB term, we have Qi a) S Q (s, a), which by the union bound, with probability at least 2. for all state-actions holds until they are visited at least my times.
(s,
24

---

In contrast to Appendix G.1, which is an off-the-shelf application of the analysis done by Strehl Littman (2008, Lemma 5), Model-Based Exploration in Mon-MDPs
G.3. Specifying The Number of Samples Required to Find A Ner--Minimax-Optimall Policy in Optimize Episodes
During optimize episodes the agent can face two types of joint state-actions: 1) state-actions that lead observing the environment reward, e.g., moving and asking for reward 2) state-actions that do not lead to observing the environment reward e.g., moving and not asking for reward. Let denote these sets the observable and the unobservable respectively.
G.3.1. NUMBER OF SAMPLES FOR THE OBSERVABLE SET
since in optimize episodes we have three unknown quantities r", ,r and p p-thtt are mappings from different input spaces- we need Lemmas F.4 and F,5 that are straight adaptations Strehl Littman (2008, Lemma and 2). By Lemma F.5, setting sa(l->)² ensures an 2--mnimaxxoopimall policy for state-actions in the observable set. We have,
(5 ST.
RR "m" r (s" amm)i T, ||P(| s,a) - p(- s, aa)ll ST.
On the other hand, if (s, a) = (s", , a", a²)) has been visited y times, its monitor reward has been observed en times, and its environment reward has been observed of times, with probabilities at least 8 1 8th and
6", holds,
2 (2 2) In 5P
|[ 8, p(- ppp11(111110 (1,1,,0)11= S
(16)
2 (2(mmmm
Rm am) rs am)) V
(17)
In(2/59
[8' a) (s a
| 5
(18)
Therefore, to find m2, the least required number of visits to (s. in optimize episodes, make connections among m2, vm, and of, If a joint state-action is visited m2 times, then we have,
= m2 S T
Σ Σ m2 = | m2 S S'E E'E.A"
where m2 p S of holds since the environment reward is observed with probability P with each visit to (s,a). To ensure Equations (16) to (18) hold with probability at least 62 until every (s, a) is visited m2 times, set 5" 5th
62
3|S|[Amm2
and 8 3,5 Alpma splitting failure probability evenly, and choose larger than the confidence intervals:
&
8 In (2 2) - In 6P]
8 (2/8") 72
8 (2/8*)
m2 max
72
72
8 In (2 S1 - 2) - In 5P
8 (2/8*)
max
72
pr2
In (2
2)
In
3 [AIma
In
6|.) ||4pmgg pmg
d2
2 max
72
pr
If 0 2 O(SS), then
8 In
G|S[|A pmg
pma
82
m2 2
pr2
which by Lemma F.1 implies
S|||||
1
|
(p72
pr2
In
TÔ2
0
pE 1
7/
In
E2
7)2
(19)
25

---

Model-Based Exploration in Mon-MDPs
If 1 < O([S]), then P
8
(2(2) 2) + In
m2 2
7²
which by Lemma F.1 implies
S
SS] | Td2
[S] 7)
1
|8| |A
m2 0
O
In
(20)
85(11
e2
- 7)
52 - 7)262
3.2 NUMBER OF SAMPLES FOR THE UNORSERVABLE SET
These state-actions cannot change the sample estimate of the environment reward and the only quantities updated by visiting them are the transition dynamics and the monitor reward. It is enough to have
8 In (2 2) in 6P
8 8ln
g
m2 2 max
72
72
Hence, similar to Appendix G.3.1, when f - O(SS),, the dominant factor around learning the sample estimates transitions and the required sample size is
S
S |A|
m2 = 0
7)4 In
(21)
EB(1 7)4
EB(1
E2(1 2)
Therefore, overall the interplay between
1 2 O((S)) and 1 and O([S)) determines the value of m2, In the worst-case
p
p
|8| |A|
m2 = 0 pe - -)1 In
(22)
52(1 7)262
G.4. Optimism of Qut
Similar to observe episodes, optimism needed to ensure the agent visits state-actions with inaccurate statistics. Let, ma be the least number of samples required to ensure RT,, P, and possible, Re are accurate. To be pessimistic in state-actions that Re cannot be computed due to their ever-lasting unobservability, we need to investigate the optimism in two cases where R can be computed and when it cannot. Consider v experiences of a joint state-action (s, a) = (s", s.h aa, a²)) and the first of experiences of the environment state-action (s*,a") in which the environment reward has been observed. Also, let V be
(s) max (s) Σ P(s' a)) V.
G.4.1. WHEN o >
Let X1;, Xei, and Xzi be random variables defined at the ith visit, where R. and RT are the immediate environment and monitor reward at the ith visit and S is the next state visited after the the ith visit:
X1 RC X = RT, X
= x=
7V(().
If (s, a) has been visited times and R has been observed or times, then: 1) the set (Xw)) has been observed, 2) least the set (X2:) is available at most ("144\1)) 3) the (X3)) is available.
Define (X1+) (X2:) and (Xa:) on joint probability space (9,F, F, F)) Using the Chemoff-Hoefidiigg inequality:
For X1s and Xas we have
P
E
1nl
1 o²
Σ
X1 2 vn
< exp
(-
P
E [21l
Σ 1m1
X2s
Yg
< exp
.Y,
2
2
1=1
26

---

Model-Based Exploration in Mon-MDPs
For X3: we have that - < X31 S
hence
(- -1-)))))
7))
P
E
X31]
Σ
X3
Y3
S exp
1
872
Define X2, and X3 on (2t P)
1
1
1 Σ
X1 = E [X11]
X1s
X2 =
E
[21]
X26
X3 = E [
X31
2
1=1
1=1
By choosing Y1= = 90
1/2 =
and Y/3
8 VD
where
Ver
v
6 6|S||AA1
|A|
m2
6
||8||A||
m2
27v In (6 S|
|A m2/62)
8
2m
8mh V
2m
==
82
82
1-y
and using Corollary F.3, we have
r²Y?
uY3(1 - -2)
+ PP P
X3
2
V1
+
Vz) S exp
+ exp
+ exp
2
882
Thus,
8m
B
82
P X1 + X2 +
X3 2
$
(23)
V
Vo
Vu
2 2
A
mn
Therefore, with probability at least 1 1
82
it must hold that X, + X2 + X3 2
gr
+
vt + 3. which is equal to
8"
2| mm2
1
g
5m
B
R
RTT +)V[(5,)) +
+
2
E
R2 + RT + (V)) Q)),.)..
1/0
Vve
VU
Vi
1=1
Therefore,
3m
B Vo
Rd d²) Rm am) + EP(6 I,,o)) +
(s)
(24)
By the union bound over S,A and m2, Equation (24) holds for all state-actions until they are visited my times, with probability least 1 4.. However, instead of the left-hand side of Equation (24), Monitored MBIE-EB follows Qupt
(
( Voo
mm
B vol
as) = (s" (a) + (s", am)) + P(s' s, (p)
P(ss'ss,
+
+
(25)
Therefore, by following the exact induction of Strehl & Littman (2008, Lemma 7), prove Qsn( a) 2 ()) Let
go
5m
B Vi
C
1/
Proof by induction is on the value iteration. Let Qup be the ith step of the value iteration for (s, a). By the optimistic initialization, we have that @o 2 Qi(s, a) for all state-action pairs. Now suppose the claim holds for 2% we have,
Siet (s, = (8 aaa) + (s" ,)") + Σ P(s') s, a, max (s', +C
=F((5",)) aa) + Rm m aa m) + 7 Σ P(8' 8, (1)++
(s ( R ) + 7 Σ P(s' (s))
(Using induction)
2 a))
(Using Equation (24))
27

---

Model-Based Exploration in Mon-MDPs
G.4.2. WHEN oF =0
If for (s, a), 1a zero, then Monitored MBIE-EB assigns -rixx R( a²) deterministically. Therefore, the previously random variable X, in Appendix G.4.1 is deterministically 0. Consequently, Equation (23) take the the form of Equation (26):
8mh
3
82
P
X2 + X3
(26)
VO
S A
m2
where 5 and 8rhh are as in Appendix G.4.1. Then, with probability at least 1 3 A|m it must hold that X₂ + X3 S
62
Vb which is equal to
mmh + V0 2 E aa ; +~V[(()) = Q((,,)) - -
Σ R m a²)) + +v[[(s)) +
Therefore,
max + R. Rs" ".".aa + > P(s 18,1 a))))(()))++++ + (3m + Vi 2 (((s.))
(27)
The rest of the proof is identical to the Appendix G.4.1's induction, but with probability at least 2/. Overall, considering Appendices G.4.1 and G.4.2, with probability at least
&
82 2 3
=1
- 56
Qop a) 2 (s, a) for all statc-actions.
G
G.S. Sample Complexity
An algorithm is probably approximately correct in MDP (PAC-MDP) if for any MDP M = (S,A,r,,,n) and 8, >> O. it finds an s-optimal policy in M in time polynomial to ((S). |A|, log }.4 rimm)) (Fiechter, 1994; Kakade, 2003; Szita & Szepesvári, 2010). In Mon-MDPs, partial observability of the environment reward naturally makes any algorithm take more time, as the lower the probability is, the more samples are required to confidently approximate the statistics of the environment reward. As a result, we extend the definition of PAC MDPs to Mon-MDPs:
Definition G.I. An algorithm is PAC-Mon-MDP minimax-optimal if for any Mon-MDP M (S,A,,, (m))) and b, 0, it finds e-optimal policy in M,, in time polynomial to (1S), |A], _ log 5 T- minimum non-zero probability of observing the environment reward embedded in f
r max 1), where p the 1 r mmux
Monitored MBIE proceeds in episodes maximum length H and it computes its action-values at the beginning of each episode. Let 6 = و2 8' . = &2 = 5. During observe episodes, as was discussed in Appendix G.I, learning transition dynamics dominant. The rewards are also (0, 1]; hence, we exactly leverage the MBII--EB's sample complexity for the the sample complexity of Monitored MBIE-EB during observe episodes
observe episodes: With probability at least
mm (
[ = (1((111111 |A
(1-1))
It means that in the worst-case scenario in each episode only one unknown state-action is visited with probability least E1(1- 7) and these visits should be repeated m, times. This specifies the order of my and x² (k) in Theorem 3.1:
mi |S [||||] R (A) m3 δ
|S| |A 63(1 7)
E1 -
Appendix G.3 showed during optimize episodes p < O(SS). the dominant factor in learning models is transition dynamics. Hence, with probability at least
55' T2 the sample complexity during optimize episodes is equal to
SS] A H
E2
If m2 2 my, the overall sample complexity (optimize and observe episodes together) is
mi |S| [S||||] |A|
=6 m2
S S1
|s| | H1
(1 -7)
E2
()))
(8(1-7)3
28

---

Model-Based Exploration in Mon-MDPs
However, p > O(S)), then the dominant factor in learning empirical models is learning the environment reward model. The sample complexity during optimize episodes when p > O((S)), with probability at least
5d'
T2 is
δ m2 |S| H - Ō ||| 62(1-1)
E (1-17))
Therefore, we conclude the worst-case scenario is when p > O([S]) and the final overall sample complexity is dominated by the optimize episodes. This sample complexity holds with probability at least 1
58' and is equal to
12
|S| |AA H ō
63
54" Defining T2
completes the proof. T
H. Mon-MDPs' Solvability
J,) Definition H.1 (Parisi et al. (2024b, Definition 1)). Let M = AS, r, ( be truthful Mon-MDP. Let M be the set of all Mon-MDPs that differ from M only in r.. Define MM to be the set of all policies in M and II = UMeeM MM to be the set
{ 5 A, R
of all Mon-MDPs' policies in M. Further, let le Te.
n, M be trajectory of length in R.H S
M when following a policy и, where EE R2 Riy # S; A, r (S), 45) almost surely. Let Tr = UMxT (U/=o'
be the set of all length trajectories in M. The indistinguishabiiity relation between Mon-MDPs M1, M2 E M is defined:
M : VL E N, T2, (r|M) P (r) almost surely.
It follows directly from the definition that the indistinguishability is equivalence relation:
1. Reflexive. Every M is indistinguishable from itself: MLM.
2. Symmetric. If Mj is indistinguishable from M2, M2 is also indistinguishable from Mr: M,TM2 + M.M2
3. Transitive. If M1 and M2 are indistinguishable, and M2 and M3. so are M1 and M3: MTLM2 A M2IM3 = M,IM,
As an equivalence relation, I partitions Mon-MDPs into disjoint classes. If [[M]r] 1, the agent can eventually identify M and its optimal policy, making M solvable. Otherwise, if [M]]]] > 1, M is unsolvable, as it is indistinguishable from at least one Mon-MDP with possibly different optimal policies.
I. Dependence On pー1 Is Unimprovable
The main distinction between Theorem 3.1's bound and MBIE-EB's for MDPs is the existence of p-1 In this section, by showing the existence of p- in tight lower bound, we conclude the dependence of Theorem 3.1 on p- is tight and essentially unimprovable. Note that lower bounds quantify the difficulty of learning for given problem for any algorithm.
To provide the lower bound, we consider the problem of a stochastic bandit with finitely-man arms imulti-armed bandit for brevity) (Lattimore & Szepesvári, 2020) as a simpler form of sequential decision-making A multi-arme bandit is a special case of MDPs where the state-space S is a singleton and the discount factor 7 equals zero. Mannor & Tsitsiklis (2004) has proved a tight lower bound on the sample complexity of learning in multi-armed bandits. We follow the setup of Mannor & Tsitsiklis (2004) as follows: The agent has + 1 arms (actions). Each arm a E kk] associated with sequence of identically distributed Bernoulli random variables X., with unknown mean Na. Here, Xat corresponds the reward obtained the tth time arm is pulled. We assume that random variables Xat for independent. The last arm = k + 1 has known mean of zero and pulling this arm terminates the interaction. A policy is a mapping that given a history, chooses a particular arm. We only consider policies that are guaranteed to eventually pull arm l +1 with probability one, for every possible vector of means [ MKk, 0) (otherwise the expected number of interaction's 's steps would be infinite). Given particular policy and multi-armed Bernoulli bandit, we let IP and denote the induced probability measure and the expectation with respect to this measure. This probability measure captures both the
1,... k + 1, and 1,...
29

---

Model-Based Exploration in Mon-MDPs
randommess in the arms and the policy. Let T be total number of interaction steps which the policy chooses arm k 1. Also, let A, denote the arm chosen at timestep t. We say that policy is (c, -cooreet if for every [M1y-... (4k, E [0, 1]
P UAT- max pa -C) -c)21 1
Theorem 1.1 (Mannor & Tsitsiklis (2004, Theorem 1)), There exists positive constants ç C22 6D, and do, such that for every k 2 2, E (0, co), and 8 E (0, 60). and for every (e, -coorrect policy, there exists some [M1..... Mix 0] such that
E T 1]
8
In particular, co and dn can be taken equal 0.125 and 0.25e respectively.
In Corollary 1.2, we derive a lower bound using Theorem I.1, where each arm's reward only observed with probability p. Corollary I.2. Under the condition of Theorem I.I with the addition that the reward of each arm is only revealed with probability 0 < p < 1 and with probability p the symbol 1 is revealed, then
E IT
2
In
pc
6
Proof. Since we only consider policies that terminates with probability one, then there exists an n E N such that T S n. Let X, denote the signal received round 112,..... We have
n
T
(A. a} +1
k
= a))
[ a} & * 1 +B LE[LIA, - af/x.=11) +1
E
==
IE
[ = at 8 # 1 +1
1 { Al = a. a +1 +1
E
(Conditional expectation's 's definition)
P ((xi+ # +
E 1 { A - a, # 11}) +
T k
A₂ = a, 8 1 +1
E
ΣΣ
-=
In 02
- 01
(Theorem I.1).
p
2
8
Thus
1] 2 In C2 pc
E [
The existence of p1 in the lower bound of Corollary 1.2 asserts that the dependence of the Monitor MBIE-EB's sample complexity on p is tight and unimprovable.
30


Reviews:
[{"review_id": "xs8uZiunSR", "reviewer": "Reviewer_VJG2", "summary": "In this paper, authors develop a model-based interval estimation algorithm for Monitored MDPs. Authors prove typical desired properties about this algorithm, and compare its performance on a suite of 24 benchmark environments to the previous SOTA for Mon-MDPs called $E^2$. The results show notable improvements.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer VJG2 for providing valuable feedback! Here, we try to address the points mentioned in order:\n\n> Appendix B.4 states that with random initialization, essentially no learning occurs, but I think a Figure showing this and comparing the performance to MBIE-EB would be useful.\n\nFigure 4.b and Figure 4.c show the lack of Directed-$E^2$'s learning and comparison with Monitored MBIE-EB. We will make a reference to these results in that section of the Appendix.\n\n> Figure 6: It looks to me like 4/24 of the environments have on par performance, not 2/24.\n\nWe agree with the reviewer that from Figure 6 alone, 4 of the environments look to have similar performance.  Due to the scaling of the y-axis, the final performance on two of the plots are difficult to evaluate. You can find rescaled results in Figure 9 in Appendix B.3 where its clear 2/24 have on-par performance, which is the basis for the claim.  We will update this figure.", "claims_and_evidence": "Claims:\n- The new model-based algorithm can fully exploit the problem structure, take advantage of a known monitor, have worst-case guarantees for unsolvable Mon-MDPs even without specific initialization, and have non-asymptotic proofs of convergence.\n\t- Evidence: Theory work in Section 3 with proofs in the Appendix.\n- MBIE-EB performs better than $E^2$ with random initialization:\n\t- Evidence: Appendix B.4 states that with random initialization, essentially no learning occurs, but I think a Figure showing this and comparing the performance to MBIE-EB would be useful.\n- The new algorithm outperforms Mon-MDP baselines such as $E^2$.\n\t- Evidence: Figure 6 Plots.", "methods_and_evaluation_criteria": "Authors compare against a suite of 24 benchmark grid environments such as \"River Swim\". These environments seem appropriate as a first test of this method, and their method outperforms the baseline, $E^2$. I wonder if there are any other relevant baselines that should be included?\n\nThey suggest future work such as pseudocounts that would expand the applicability of the approach to non-enumerable state spaces. It seems reasonable for this to be left to future work rather than included in this paper.", "theoretical_claims": "No.", "experimental_designs_or_analyses": "Authors provide 95% confidence intervals, and hyperparameters are clearly stated in Appendix C.", "relation_to_broader_scientific_literature": "This paper extends the classic MBIE algorithm to Mon-MDPs.", "essential_references_not_discussed": "Unknown", "other_strengths_and_weaknesses": "The main weakness of the paper, in my opinion, is that I am not sure how widely used Mon-MDPs are. Within domain, the algorithm suggested in the paper is certainly good, but without further knowledge of this literature, I am not sure what other related extended MDP formulations have similar results known.", "other_comments_or_suggestions": "Figure 6: It looks to me like 4/24 of the environments have on par performance, not 2/24.", "questions_for_authors": "Not at this time.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FuVDPpfGkS", "reviewer": "Reviewer_fk7j", "summary": "This work extends model-based interval estimation with exploration bonus (MBIE-EB), a well-known model-based exploration algorithm for MDPs with PAC guarantees, to the monitored MDP (Mon-MDP).\n\nThe monitored MDP relaxes the assumption that the reward is observed at every time step and, instead, let this be determined by a monitor.\nThis monitor can be, for example, a human giving rewards to the agent (but only if they are present) or depend on an unreliable / expensive sensor.\nThis monitor itself is a state-full (Markovian) entity function that observes the true environment and provides a \"monitor\" reward and an environment reward.\nThe goal is to optimize for the true environment return plus the monitor reward.\n\nMBIE-EB works on constructing optimistic MDPs to ensure the problem is fully explored, based on counting visits.\nThe extension proposed here has two parts.\nFirst, the optimistic counting is also applied to the transition and reward function of the monitor.\nSecond, to good worst-case performance when rewards of certain state-action pairs are never observable, the agent becomes pessimistic after a certain horizon (hyper parameter).\n\nThis method is compared to directed exploration-exploitation (Directed-E2) on several benchmarks reported in Directed-E2's paper.\nThere are no other baselines, which is understandable given the lack of SOTA due to the recency of Mon-MDP's definition, but the experimental section is insightful and convincing.\nLastly, the method comes with sample complexity, which seems to be based on MBIE-EB's original proof (techniques), but contains some novel components.\n\n## update after rebuttal\n\nThe rebuttal period has not changed my mind regarding the (positive) score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer fk7j for providing valuable feedback! Here, we try to address the points mentioned in order:\n\n> It would have been nice to see some non Mon-MDP algorithms performance, especially on MDPs that are less obviously designed with these Mon-MDP algorithms in mind. Similarly, some ablation studies on parameter robustness and different versions of the proposed method would have been insightful and helpful.\n\n In Figure 9 in Appendix B.3 the first column shows the performance on traditional MDPs. Parisi et al. (2024a) showed the superior performance of of Directed-$E^2$ against conventional exploration strategies such as $\\varepsilon$-greedy, optimistic initialization, $\\varepsilon$-greedy with count bonuses, $\\varepsilon$-greedy with UCB bonus and $\\varepsilon$-greedy with [long-term UCB bonus](https://www.mdpi.com/1999-4893/15/3/81) [Parisi et al., 2022]. Our conclusion is that when our proposed algorithm, Monitored MBIE-EB, outperformed Directed-E$^2$, it simultaneously outperformed five other baselines as well.  We will make this more explicit in the final version.\n\nWe have run ablation studies on the significance of pessimism and observe episodes in which the agent only seeks observability of the environment reward. The findings show that both are needed to achieve the results in the paper. We’ll add the ablation experiments to the appendix in the final version. \n\n> It would have been nice to introduce / describe KL-UCB in more depth, at least define it mathematically.\n\nWe have given the explicit formula of KL-UCB in Appendix E, page 26, line 1383. We will add a footnote to the main body of the paper with the formula and reference to the appendix.", "claims_and_evidence": "= Worst-case performance\n\nThe method is claimed to learn policies for worst-case Mon-MDP scenarios (of never observing rewards in some state-action pairs).\nThis is well tackled both intuitively when introducing the method, as well as in empirical studies on convincing domains.\n\n= Sample complexity guarantees.\n\nIt is claimed to have the first sample-complexity guarantees and the proof _looks_ good.", "methods_and_evaluation_criteria": "See summary, the method is evaluated on Mon-MDP benchmarks where they show their proposed method reliably outperforms the SOTA (for which the domains were designed).\nIt would have been nice to see some non Mon-MDP algorithms performance, especially on MDPs that are less obviously designed with these Mon-MDP algorithms in mind.\nSimilarly, some ablation studies on parameter robustness and different versions of the proposed method would have been insightful and helpful.", "theoretical_claims": "The method is shown to converge within finite samples, depending on parameters inherited form MBIE-EB and the minimum non-zero probability that a reward is seen `p`.\nIn particular, the sample complexity is `O(... 1/p)`.", "experimental_designs_or_analyses": "The usual experiments on performance over time, which is fine.", "relation_to_broader_scientific_literature": "This work is specifically targeting Mon-MDPs, which is a rather niche (but I can see important) problem setting.\nThe contributions are unlikely to have broad influence in other fields as, instead, it is applying (non-trivially) an existing algorithm / proof to their use-case.", "essential_references_not_discussed": "Nothing came to my mind.", "other_strengths_and_weaknesses": "Nothing comes to mind.", "other_comments_or_suggestions": "It would have been nice to introduce / describe KL-UCB in more depth, at least define it mathematically.", "questions_for_authors": "Nothing comes to mind.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "H2FH3kJSKI", "reviewer": "Reviewer_gjFL", "summary": "The current paper consider the task of bounding the sample complexity of exploration in monitored MDP where the reward of the environment is observed only for some of the state action pairs and where the minimum non zero probability of observing an environment reward is lower bounded by $\\rho$.\n\nInteresting the authors bound the sample complexity of exploration aslo for Non solvable Mon-MDP using as comparator not the optimal policy but the minmax policy which is optimal in the wrost case MDP. That is, the one that has minimum reward in the state action pairs for which the environment never reveals the reward function.\n\n### After rebuttal\n\nMy opinion remains positive.\nI think that the lower bound will improve the paper. I hope you can really include it in the final version.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer gjFL for providing valuable feedback! We are glad you found the algorithmic derivation very well explained. Here, we try to address the points mentioned in order:\n\n> An additional theoretical result that the author could try to obtain is the regret from the initial distribution ( allowing the agent to reset from it). In this way the author could argue that they can recover a policy almost as good as the minmax policy in solving the Mon-MDP. The current guarantees only say that the recovered policy is as good as the minmax one for states that are visited by the learner after a long enough number of steps. I think that this is an interesting future direction that the authors could pursue.\n\nWe thank the author for the suggestion! We agree that would be an interesting future direction.\n\n> I think the authors should add a discussion motivating this metric and referring to these previous works.\n\nWe agree.  We’ll cite the suggested works and elaborate more on the motivation behind sample complexity in the final version of the paper.\n\n> I think that the author should add a pseudocode of the algorithm.\n\nWe’ll add pseudocode to the appendix in the final version of the paper.\n\n> Have you tried to prove a lower bound to show that the dependence on $\\rho^{-1}$ is necessary?\n\nWe felt the dependence was indeed necessary, but hadn’t thought about making the argument formal until your question.  One can construct hard examples from simple single-state Mon-MDPs (embodying a bandit problem), where arm rewards are only observable with probability $\\rho$.  Intuitively, since it will take $O(1/\\rho)$ pulls to observe any arm’s reward, this should give exactly this lower bound.  We will aim to make this formal (building off of Mannor and Tsitsiklis’s (2004) bandit PAC-bounds) in the final version.", "claims_and_evidence": "Yes, there is clear and convincing evidence.", "methods_and_evaluation_criteria": "Yes, the proposed experiments and theory make sense for the considered problem.\n\nAn additional theoretical result that the author could try to obtain is the regret from the initial distribution ( allowing the agent to reset from it).\nIn this way the author could argue that they can recover a policy almost as good as the minmax policy in solving the Mon-MDP. The current guarantees only say that the recovered policy is as good as the minmax one for states that are visited by the learner after a long enough number of steps.\nI think that this is an interesting future direction that the authors could pursue.", "theoretical_claims": "The proofs seem correct. I had a quick look at all of them.", "experimental_designs_or_analyses": "The experiments are complete. They are limited to tabular tasks but it makes sense to run experiment exactly in the same setting for which the theory applies.", "relation_to_broader_scientific_literature": "I think that the related literature is well covered.\nHowever, I think that the author should motivate the metric that they bound in their theoretical guarantees a bit better.\nIn particular, they should say that this quantity is known as sample complexity of exploration and it was first studied in Kakade's PhD thesis.\n\nhttps://homes.cs.washington.edu/~sham/papers/thesis/sham_thesis.pdf Theorem 8.3.2\n\nAlso there are several follow up works looking at the same metric\n\nhttps://proceedings.mlr.press/v19/szita11a/szita11a.pdf Definition 5.1\n\nLattimore & Hutter PAC Bounds for Discounted MDPs\n\nI think the authors should add a discussion motivating this metric and referring to these previous works.", "essential_references_not_discussed": "See above", "other_strengths_and_weaknesses": "The algorithmic derivation is very well explained. I particularly liked the steps explaining why plain UCB approaches would fail for excessive optimism and why assigning $r_\\min$ to unobserved state action pairs would fail due to excessive pessimism.", "other_comments_or_suggestions": "I think that the author should add a pseudocode of the algorithm.", "questions_for_authors": "Have you tried to prove a lowe rbound to show that the dependence on $\\rho^{-1}$ is necessary ?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "XA2BVdHezW", "reviewer": "Reviewer_TsqN", "summary": "This paper considers model-based reinforcement learning under partially observable rewards. In classical reinforcement learning, the agent always receives a reward upon executing an action in the current state of the underlying MDP. However, in practical scenarios, such as when a human provides intermittent rewards, this assumption may not hold.\n\nThe work builds on the recent model of Monitored MDPs, where the agent interacts with both the environment and a monitor (another MDP). The monitor has its own state and action spaces, both observable to the agent. The agent operates in the joint state space, executing joint actions and receiving up to two rewards (monitor and environment), both through the monitor. The crucial difference is that the monitor may hide environment rewards from the agent, though observed rewards are assumed to be truthful.\n\nDue to partial observability of rewards, globally optimal behavior may be unattainable when some rewards are always hidden (unsolvable Mon-MDPs). Thus, the goal is to derive a minimax-optimal policy, ensuring robustness under worst-case assumptions on unobservable rewards.\n\nTo address this, the authors extend the MBIE-EB algorithm to Mon-MDPs, the primary challenge being to balance exploration-driven optimism with safety-driven pessimism. They adapt the exploration bonus of MBIE-EB by distinguishing previously observed environment rewards and leveraging KL-UCB to estimate upper confidence bounds on the probability of reward observability. This fosters initial optimism for exploration, which for unobservable rewards shifts to pessimism in the long-run. \n\nThe key theoretical result is an MBIE-EB-like sample complexity guarantee for the algorithm to arrive at a near minimax optimal policy, which they prove to be polynomial in parameters corresponding to confidence and proximity to the minimax-optimal expected reward.  This is subsequently evaluated experimentally on a range of Mon-MDP environments, primarily comparing the new MBIE-EB-based approach to existing techniques for Mon-MDPs.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer TsqN for providing comprehensive and in-depth feedback!  We are glad you found the paper well-written and easy to follow. Here, we try to address the points mentioned in order:\n\n>  I’m wondering to what extent this assumption of full observability restricts potential applications of this theoretically compelling framework, and whether it might be relaxed into a partially observable state and reward setting (like Mon-POMDPs?)\n\nAs you have mentioned, the introduction of the Mon-MDPs is not a contribution of our work, but we find it useful to share our thoughts around your insightful scrutiny around the applicability of Mon-MDPs.\n\nWe agree that grid-world domains do not represent the real-world applicability of most algorithms. Our choice to run experiments on these domains is because the Mon-MDP framework is relatively new and controlled small-scale experiments help shed light on the understanding of various aspects of this framework. Following the original Mon-MDP paper [Parisi 2024b], we have assumed that the agent receives a joint state from the environment and the monitor. Since these are both MDPs, they could likely be modeled by POMDPs instead. In such a (novel) framework, we imagine the agent would receive the joint observation and techniques from the POMDP literature could be adapted in future work. \n\n\n>  The definition of the equivalence class [M]_I for Mon-MDPs under reward observability is not quite self-contained here and should probably include a little clarification on state and action spaces being fixed as per [Parisi et al., 2024b] . The description “the set of all Mon-MDPs that the agent cannot distinguish” confused me for a second, since this may also include much larger but, e.g., bisimilar Mon-MDPs, also rendering the set not a singleton for solvable Mon-MDPs.\n\nAs you have pointed out, the definition is given by [Parisi et al 2024b]. But we revisit it in the appendix of the final version and further clarify the concept.\n\n\n>To what extent does the assumption of a fully observable monitor state space restrict the applicability of this approach in real-world scenarios? Are there practical examples where this assumption is clearly justified?\n\nIf the state of the monitor and the environment are fully observable to the agent, then Mon-MDPs would suffice.  We feel that many monitored settings match the fully observable criteria.  Often the RL practitioner is instrumenting the system that provides rewards, and so the full state is more easily known and possibly provided to the learning agent (e.g., the status of sensors that measure reward, or their locations in the world and under what conditions they provide signals).  Human monitors, though, might be a good example that would not fit the fully observable setting as they typically would have internal state that could not be provided to the agent.\n\n> Would an extension of this to partially observable states (i.e., unobservable monitor states) be possible (like Mon-POMDPs)?\n\n Likely - please see our answer above.\n\n> How does this approach scale to larger environments in higher dimensions? What are the limiting factors, e.g., compared to plain MBIE-EB?\n\nThe biggest limiting factor is the direct dependency on the counts of visiting state-action pairs or observing the environment rewards (which applies to other tabular methods, including MBIE-EB). As pointed out in the paper in Discussion section Iine 416, using pseudocounts could ameliorate this shortcoming to some extent, which have been applied to improve exploration with Deep RL methods [Bellemare et al., 2016; Tang et al., 2017]. The other limitation (distinct from MBIE-EB) is the computation time of the KL_UCB term, which does not have a closed-form. However, this term can be replaced with a typical $\\frac{\\alpha}{\\sqrt{N(s, a)}}, \\alpha > 0$ bonus. This new bonus again can be extended by pseudocounts.", "claims_and_evidence": "The claims of the paper are well supported. Theoretical claims build on established results from the literature, with proofs given for novel contributions. Practical claims are backed by the experimental evaluation.", "methods_and_evaluation_criteria": "The considered model class of Mon-MDPs is very recent, therefore, the range of existing benchmark environments is understandably limited. The paper evaluates the proposed approach on a small established benchmark and several seemingly novel synthetic benchmarks. Their choice is reasonable and they cover a range of interesting, though small-scale setups. Since the algorithm is model- and counting-based, all environments are grid worlds.", "theoretical_claims": "The main theoretical claim builds on established results from the literature. I reviewed the corresponding proofs in the appendix and found no inaccuracies or gaps.", "experimental_designs_or_analyses": "The benchmark environments, hyperparameters, and experimental setups are well documented and reasonable. The results also appear consistent and well-founded.", "relation_to_broader_scientific_literature": "The paper builds and extends on the recent literature on Mon-MDPs introduced by [Parisi et al., 2024b] ( AAMAS 2024), and partially observable rewards [Parisi et al., 2024a] (NeurIPS 2024). The authors extend the MBIE-EB algorithm from [Strehl and Littman, 2008] to finite-state Mon-MDPs, also leveraging upper confidence bounds as per [Garivier and Cappé, 2011] for the estimation of the chance to observe rewards. In combination, this results in a model-based RL algorithm for Mon-MDPs which they compare to the Directed-E^2 algorithm from [Parisi et al., 2024a].", "essential_references_not_discussed": "None that I'm aware of.", "other_strengths_and_weaknesses": "# Strengths\n\nThe paper is overall very well written and easy to follow. The authors do a good job in keeping the paper self-contained and motivating their contributions. The proposed algorithm is simple and elegant, yet effective as both formally proven in their main theoretical results and practically validated in the experimental evaluation, primarily comparing it to the existing Directed-E^2 algorithm for Mon-MDPs. \nThe theoretical results are compelling, extending MBIE-EB-like guarantees from standard MDPs to the more complex model of Mon-MDPs. The evaluation demonstrates a clear advantage of the new algorithm over existing methods, especially in unsolvable Mon-MDPs where some rewards are never observable, for which, e.g., the Directed-E^2 algorithm seems to struggle.\n# Weaknesses\nI am wondering about the practical applicability of the Mon-MDP setup. The authors motivate the model with, for example, a human in the loop who provides rewards but may not always be present, thus making some rewards unobservable. While this makes sense conceptually, it also seems like a fairly coarse-grained approach in which all rewards are either observable or not during certain time periods, not emitting much more exploitable structure.\nAt the same time, the model class assumes full observability of the monitor’s state space by the agent, and it’s not entirely clear how this would extend to, for example, a human-in-the-loop setting or other complex scenarios beyond a simple present/not-present setup. The monitors the authors consider are mainly random, small “button-like” states (on/off), or cases where the agent must determine which part of the monitor to consult. I’m wondering to what extent this assumption of full observability restricts potential applications of this theoretically compelling framework, and whether it might be relaxed into a partially observable state and reward setting (like Mon-POMDPs?). However, I also recognize that this may not be a shortcoming of the current paper, since it does not introduce the model class itself but proposes a new algorithm that improves upon existing ones.\nThe experimental evaluation is broad and covers a range of grid-worlds with diverse features and complications, all tested with different monitor designs. However, these environments are relatively small, with the largest being a 6x6 2D grid-world. While smaller setups are typical in model-based approaches, it would be interesting to see how this method scales to larger or higher-dimensional domains.", "other_comments_or_suggestions": "- Line 126: Footnote 1 should probably be Footnote 3.\n- Line 174: r_max should probably be r_min.\n- Line 170: The definition of the equivalence class [M]_I for Mon-MDPs under reward observability is not quite self-contained here and should probably include a little clarification on state and action spaces being fixed as per [Parisi et al., 2024b] . The description “the set of all Mon-MDPs that the agent cannot distinguish” confused me for a second, since this may also include much larger but, e.g., bisimilar Mon-MDPs, also rendering the set not a singleton for solvable Mon-MDPs.", "questions_for_authors": "1. To what extent does the assumption of a fully observable monitor state space restrict the applicability of this approach in real-world scenarios? Are there practical examples where this assumption is clearly justified?\n2. Would an extension of this to partially observable states (i.e., unobservable monitor states) be possible (like Mon-POMDPs)?\n3. How does this approach scale to larger environments in higher dimensions? What are the limiting factors, e.g., compared to plain MBIE-EB?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The authors did a good job of addressing the technical concerns raised by the reviewers. The only unaddressed concern(s) could be paraphrased as: Are the authors really solving a problem worth solving? It's disappointing that this issue was raised by multiple reviewers, yet the authors didn't have a compelling answer.
Decision: Accept (poster)