Efficient RL with Impaired Observability: Learning to Act with Delayed and Missing State Observations
Authors: Minshuo Chen
Yu Bai
H. Vincent Poor
Mengdi Wang
Venue: NeurIPS 2023 poster (2023)
Keywords: Delayed and missing observations
MDPs
efficient regret bounds

Abstract: In real-world reinforcement learning (RL) systems, various forms of {\it impaired observability} can complicate matters. These situations arise when an agent is unable to observe the most recent state of the system due to latency or lossy channels, yet the agent must still make real-time decisions. This paper introduces a theoretical investigation into efficient RL in control systems where agents must act with delayed and missing state observations. We establish near-optimal regret bounds, of the form $\tilde{\mathcal{O}}(\sqrt{{\rm poly}(H) SAK})$, for RL in both the delayed and missing observation settings. Despite impaired observability posing significant challenges to the policy class and planning, our results demonstrate that learning remains efficient, with the regret bound optimally depending on the state-action size of the original system. Additionally, we provide a characterization of the performance of the optimal policy under impaired observability, comparing it to the optimal value obtained with full observability.

Efficient RL with Impaired Observability: Learning to Act with Delayed and Missing State Observations
Minshuo Chen'
Yu Bai
H. Vincent Poor
Mengdi Wang'
Princeton University
Salesforce Research
Abstract
In real-world reinforcement learning (RL) systems, various forms of impaired observability can complicate matters. These situations arise when an agent is unable to observe the most recent state of the system due to latency or lossy channels, yet the agent must still make real-time decisions. This paper introduces theoretical investigation into efficient RL in control systems where agents must act with delayed and missing state observations. We establish near-optimal regret bounds, of the form O (lL/polyyHH)). observation settings. Despite impaired observability posing significant challenges to the policy class and planning, our results demonstrate that learning remains efficient, with the regret bound optimally depending on the state-action size of the original system. Additionally, we provide characterization of the performance of the optimal policy under impaired observability, comparing the optimal value obtained with full observability.
for RL in both the delayed and missing
Introduction
In Reinforcement Learning (RL), an agent engages with environment in sequential manner. In an ideal setting, at each time step, the agent would observe the current state of the environment, select an action perform, and receive reward Smallwood and Sondik [1973], Bertsekas [2012], Sutton and Barto [2018], Lattimore and Szepesvári [2020]. However, real-world engineering systems often introduce impaired observability and latency, where the agent may have immediate access the instant state and reward information. In systems with lossy communication channels, certain state observations may even be permanently missing, never reaching the agent. Nevertheless, the agent is still required to make real-time decisions based on the available information.
The presence of impaired observability transforms the system into complex interactive decision process (Figure 1), presenting challenges for both learning and planning in RL. With limited knowl- edge about recent states and rewards, the agent's policy must extract information from the observed history and utilize to make immediate decisions. This introduces significant complexity to the policy class and poses difficulties for RL. Moreover, the loss of information due to permanently missing observations further hampers the efficiency of RI. methods. Although a na've approach would involve augmenting the state and action space to create fully observable Markov Decision Process (MDP), such a method would lead to exponential regret growth in the state-action size.
Why existing methods do not work. One may be tempted cast the problem of impaired observability into a Partially Observed MDPs (POMDPs). However, this would not solve the problem. In POMDP, the system does reveal its instant state to the agent but provides observation conditioned on the latent state. POMDPs are known to suffer from the curse of history Papadimitriou and Tsitsiklis [1987], Bertsekas [2012], Krishnamurthy [2016], unless additional assumptions are imposed. Existing efficient algorithms focus on subclasses of POMDPs with decodable or distinguishable partial observations Jin et [2020], Uehara et al. [2022]. Zhan et al.
emission state
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Real-Time Action
Policy
On (-18h-d Oh Oh-d. (h-1)
Agent
Environment
Time is Observation Bia-d
Delay
Ob-- Up-1
Missing
Figure 1: Reinforcement learning with impaired observability. At time h, the agent only observes the past state Sh-d and actions Oh-ds..., a/-1- The policy depends on the observed information.
[2022], Chen et al. [2022], Liu et al. [2022]. Zhong et al. [2022], Chen et al. [2023], where the unseen instant state can be inferred from recent observations. Unfortunately, MDPs with impaired observability do not fall into these benign subclasses. The reason behind this is that at each time step, a new observation, if any, is in fact a past state. Viewing as an emission state of the current one leads to a time reversal posterior distribution depending on the underlying transitions, which suffers from the curse of history and makes the POMDP intractable. The problem becomes even harder if some observations get missing.
Empirical evidences suggested that efficient RL is possible even with impaired state observability Lizotte et al. [2008], Liu et al. [2014], Agarwal and Aggarwal [2021]. However, theoretical under- standing of this problem is very limited. One notable work Walsh et al. [2007] studied learning with constant-time delayed observations. They identified subclasses of MDPs with nearly deterministic transitions that be efficiently learned. Beyond this special case, efficient RL with impaired observability in MDPs with fully generality remains largely open.
Some recent works studied delayed feedback in MDPs Yang et al. [2023], Howson et al. [2023]. It is a fundamentally different problem where the agent's policy can still access real-time states but learning uses delayed data. Our problem is fundamentally harder because the agent's policy can only access the lossy and delayed history. See Section 1 for more discussions.
Our results. In this paper, we provide algorithms and regret analysis for learning the optimal policy in tabular MDPs with impaired observability. Note that this optimal policy is a different one from the optimal policy with full observability. To approach this problem, we construct an augmented MDP reformulation where the original state space is expanded to include available observations of past state and an action sequence. However, the expanded state space is much larger than the original one and naïve application of known methods would lead to exponentially large regret bounds. In our analysis, we exploit structure of the augmented transition model achieve efficient learning and sharp regret bounds. The main results are summarized as follows.
For MDPs with stochastic delays, we prove a sharp Õ(1* (SK) regret bound (Theorem 4. comparing to the best feasible policy, Here S and are the sizes of the original state and action spaces, respectively, H is the horizon, and K is the number of episodes. Here we allows the delay to be stochastic and conditionally independent given on current state and action. Moreover, we quantify the performance degradation of optimal value due to impaired observability, compared to optimal value of fully observable MDPs (Proposition B.2). We also showcase Proposition 4.2 that short delay does not reduce the optimal value, but slightly longer delay leads to substantial degradation.
For MDPs with randomly missing observations, we provide an optimistic RL method that provably achieves Õ(V 52 AK) regret (Proposition 5.1). We also provide sharper Ö(H* /SAK) regret in the case when the missing rate is sufficiently small (Theorem 5.2).
To our best knowledge, these results present first of theories for RL with delayed and missing observations. Remarkably, our regret bounds nearly match the minimax-optima regret of standard MDP in their dependence on S, A (noting that the target optimal policies are different in the two cases). It implies that RL with impaired observability are provably as efficient as RL with full observability (up to poly factors of H).
Related work. Efficient algorithms for learning in the standard setting of tabular MDPs without im- paired observability has been extensively studied Kearns and Singh [2002]] Brafman and Tennenholtz [2002], Jaksch et al. [2010], Dann and Brunskill [2015], Azar et al. [2017], Agrawal and Jia [2017],

---

Jin et al. [2018], Dann et al. [2019], Zanette and Brunskill [2019], Zhang et al. [2020], Domingues et al. [2021], where the minimax optimal regret is O D(VIISSAK Azar al. [2017], Domingues et al. [2021].
The delayed observation studied in this paper is related to delayed feedback in Howson et al. [2023], Yang et al. [2023], yet the setup is fundamentally different. In delayed feedback, an agent sends a policy to the environment for execution. The environment executes the policy on behalf of the agent for an episode, but the whole trajectory will returned to the agent after some episodes. The policy executed by the environment is able to "see" instant state and reward. It is Markov and not played by the agent. Our setting concerns learning executable policies when delayed or missing states appear within an episode. The policy is no longer Markov and can only prescribe action based on history. Therefore, the algorithms and analyses for delayed feedback MDPs are not applicable to our settings.
Despite the distinct settings, there are existing fruitful results in efficiently learning MDPs or bandits with delayed feedback. Stochastic delayed feedback in bandits is studied in Agarwal and Duchi [2011], 1]. Dudik et al. [201 I]. Joulani et al. [2013], Vernade et al. [2017, 2020], Gael et al. [2020], Lancewicki al. [2021]. 1]. In the more challenging setting of reinforcement learning, Howson et al. [2023] considers tabular MDPs and Yang et al. [2023] generalizes to MDPs with function approximation and multi-agent settings.
On the other hand, results analyzing MDPs with missing observations are limited in literature, although missing data is a commonly recognized issue in applications Garcfa-Laencina al. [2010], Jerez et al. [2010], Little et al. [2012], Emmanuel et al. [2021]. One notable result is Bouneffouf et al. [2020] for bandits with missing rewards.
Notation: For real numbers a, b, we denote a A = min b]. In episodic MDPs, we use the superscript & to denote the index of episodes, and the subseript h to denote the index of time. We denote anj = {a........ } as the collection of actions from time i to j. For two probability distributions y and v, we denote their total variation distance as || w/|TVV
MDP preliminary: An episodic MDP is described by a tuple (S. A, H, R, P), where S,A are state and action spaces, respectively, If is the horizon, R = { } is the reward function and P = {ps. hh=1 is the transition probability. We primarily focus on tabular MDPs, where S = |S| and A = [A] are both finite. We also assume that the reward is uniformly bounded with ||r S 1 for any h. An agent will interact with the environment for K episodes, hoping to find a good policy to maximize the cumulative reward. Within an episode, at the h-th step, the agent chooses an action based on the available information of the environment. After taking the action, the underlying environment produces a reward and transits to the next state. With full state observation, a policy π maps instant state to an action an action distribution. Given such a policy æ, the value function is (s1) = ET - (s ax) sn where E= is the policy induced expectation.
2 Problem formulation
In this work, we study MDPs with impaired observability. We focus on two practical settings: 1) delayed observations and 2) missing observations.
2.1 MDP with delayed observations
In any episode, we denote da, E 10,1,...} as the observational delay of the state and reward at step h. That is, we receive 8 and rı at time h + dr. The delay time d, can be dependent on the state 8s, and action as at time h. To facilitate analysis, observations for step and + 1 as An = dh+1 - dh. With delays, at time h, the nearest observable state is denoted as St, where 4a = argmax (1 Σ A; < hJ. Then the executable policy class
denote the inter-arrival time between the arrival of
Toxe
(- at 1) for h = 1, 1...., H)
chooses actions depending on the nearest visible state and history actions. We impose the following assumption on the interarrival time.
Assumption 2.1 The interarrival time A, takes value in (0, 1,... J. The distribution Da(sn, an) of An can depend on (s%, ax), but is conditionally independent of the MDP transitions given (sh, or).
3

---

Assumption 2.1 does not impose any specific distributional assumption on An. but only requires that the delayed observations arrive in order and at each time step, there is most one new visible state and reward pair (Á, 2 0). A widely studied example of delays in literature is that the inter-arrival time is geometrically distributed Winsten [1959]. Then the observation sequence { + d, is known as Bernoulli process, which is understood as the discretized version of Poisson process.
Our delayed observation setting is newly proposed and substantially generalizes the Constant Delayed MDPs (CDMDPs) studied in Brooks and Leondes [1972]. Bander and White III [1999], Katsikopoulos and Engelbrecht [2003], Walsh al. [2007]. When A being deterministic for all h 2 1 and our observation delay coincides with CDMDPs. In CDMDPs, a new past observation is guaranteed to arrive each time step. However, our delayed model can result no new observation some
time steps.
Observation delay leads difficulty in planning, as the agent only infer the current state and then choose an action. Therefore, the policy is naturally history dependent. We summarize the interaction protocol of the agent with the environment in Protocol 1. At the end of each episode, we can collect
Protocol Interaction between the agent and the environment with delayed observations
1: for episode 1, ......................... K do
2: for time h .,.... H do
3: The agent observes pair of new, if any, state and reward (s of By memory, the agent
also has access to past actions a
4:
The agent plays action af according to some executable policy क Ieexec- The environment transits to next state sh+ Pa (-1sf at), which is unobservable to the agent. The environment also decides the delay at step h as di d A and 1+1-
5:
6: end for
7: The environment sends all unobserved pairs of state and reward as well their corresponding delay time to the agent.
8: end for
all delayed observations, however, these observations are not used in planning. In reality, the agent can collect these observations by waiting after time H. Protocol is similar hindsight observability in POMDPs studied in Lee et al. [2023]. Yet their analysis for POMDPs is not directly transferable to settings mentioned in the introduction.
2.2 MDP with missing observations
In addition the stochastic delay in observations, also consider randomly missing observations. In applications, an agent interacts with the environment through some communication channel. The communication channel is often imperfect and thus, observation can be lost during transmission. This type of missing is permanent and we describe in the following assumption.
Any pair of observation (state and reward) is independently observable in the communication channel. The observation rate is Å depending on h, but independent of the MDP transitions. Moreover, there exists a constant λ such that Ay 2 A for any h. The agent will be informed when observation is missing.
Assumption 2.2
Equivalently, the missing observation rate in Assumption 2.2 is 1 - A and assumes the upper bound of 1 Ag. We will show later that this missing rate directly influences the learning efficiency in Section 5.
3 Construction of augmented MDPs
To tackle the limited observability, we expand the original state space and define an augmented MDP. It will serve as the basis for our subsequent theoretical analysis.

---

3.1 Augmented MDPs with expected reward
In the remainder of this section, we focus on the delayed observation case and defer the missing case to Section 5. Define = {Sty at, de,, the augmented state, where òt, E [0, Ar, is the delayed steps after observing (St,, rt,, Let Sang denote the augmented state space all possible r's. Then the original MDP with delayed observations can be reformulated into state-augmented one MDP aug (Saug: A, H, Rang: Paug). The reward is defined as
Thaang The an) = E [rn (8h, an) [Th, an),
which is the expected reward given the nearest past state St, and history actions atash. We can define belief distribution by (s(m)) = (s, = 8 T/). Then ahk (Th, ah) = Ea (cIra) (rs, an)]. Belief distributions are widely adopted in partially observed MDPs Ross et al. [2007], Poupart and Vlassis [2008]. We will frequently use the belief distribution to study the expressivity of Iexec in Section 4.2.
The transition probabilities Pa Pang are sparse. For any Th {8t, at St,, and Th41 (8t4417 41 J. we have
anr ( Th++ Th, (h)
Condition
Ma (Th, Th+ Ooelay (St,, ae, Se, Pen, (Sta- 18t2. aep. Ma 11 Odelay (se,, aen, 8en))
if 8
0 and 84+1 bn
if dent1 St, + and th+11 = th otherwise
where Ma (Ths Th+1) indicates whether the rolling actions are matched, i.c..
Ma(Ti, Th+1) 11 (a at, 11th-1
and Odeaay (st, au, Se,)) is defined as
P(As, Sen |sc, aen
Odelay (St,, atp Sen)) ) TP(Ai, Sen 1st ata Sea) Eoco,, P(Ds, 8|st, oth)
The factored form of dellay (Stz. Atg. Seg Pr,, (st,, 1a |t,, ai,,) follows from the conditional indepen- dence in Assumption 2. We define Q-functions and value functions as follows. For any The On and policy æ E Texecs we have
Qi (Th, an) = ET
Th aug (Thi, aax) Thi and
Ving (Tn) (QT,.oug (TR, +), T (-ITa))
We note that VI is equivalent to Vinn for the same executable policy æ E Toxer- We also denote Puy the transition operator corresponding to Paug. It can be checked that
Q aug (Th, an) = ahg (Tu, an) + aPh Vir Vi, (Th, an).
MDP also appears in makes all the policies in Ieex executable and Markov. Meanwhile, the reward function keeps track of all the expected reward for H steps. Although the expanded state space Saug is much more complicated than the original state space S, the sparse structures in the transition probabilities still allow an efficient exploration. We note that Ph,aug only depends on the delay distribution and one-step Markov transitions. However, there is still one caveat for learning in MDP aug the reward function depends belief distributions, which involve multi-step transitions.
3.2 Augmented MDPs with past reward
To tackle the aforemennioned challenge, we further define MDP = (Sang A, H, Raug, Paug) that shares the optimal policy in MDP ang with enlonged horizon H = 2H. The state space Sang consists of any Tы = {S1, :tA H. 8r,, Comparing to Sangs we cut off the action at horizon H, since as for h > H has no influence on the state and reward in time [1, H). The reward function is defined as
ang (Th, ap) Tta (Se,, Gr,. 11r = 0) E
5

---

By definition, Faug (Te ah) is a past reward. More importantly (T.. o4) zeros out rewards outside the original horizon H. Meanwhile, between the arrival two consecutive state observations. the reward only counts once. Lastly, the transition probabilities are
Ph aue Th+11 Thi an.)
Condition
Ma (Th, Th+ delloy (Stg Oayy Seg )ra, (St. |8tn Otn)
if St 0, (++1 ln + 1 and h < H
Ma (Th, Th++)((1 Odeley (Sta, Oeg 8ta))
if Seass = di, + 1,, 1x+11 = tn and < H
(Th Th41 Pea (5ea +1 18t, (ta.)
if dea+1 = 0, 1+t1 4n and h > H
otherwise
We interpret the transitions follows. When h S H, the transition is the same as MDP aug. When H, we simply wait for unobserved states and rewards to come. As mentioned, actions taken beyond time are irrelevant. build an equivalence the expected values MDP MDPaug
aug and MDP aug Proposition 3.1. Let MDP aug and MDP aug be defined in the previous paragraphs. Then for any initial state Ti and any policy {TT 1
ITxxxo> holds that
H
E
Σ
awg (Th, an)
11
Ex
Σ Th The and
where in the right-hand side, the policy for steps H + 1 to is arbitrary.
The proof is provided in Appendix A.1. Proposition 3.1 implies that learning in MDP until time H is equivalent to that in MDP aug for H steps.
4 RL with delayed observations and regret bound
In this section, provide regret analysis of learning in MDPs with stochastic delays. For the sake of simplicity, we assume the reward is known, however, extension to unknown reward causes no real difficulty. Motivated by the augmented MDP reformulation, in Algorithm 2. In Line 5, unobserved states and rewards are returned to the agent as described in Protocol Using the data set, we construct bonus functions compensating the uncertainty in one-step transitions of the original MDP. This largely sharpens the confidence region, yet still ensures a valid optimism. We emphasize that in Line 9, we are planning on MDP sug involving the augmented transitions and expanded states of E Saug. Only in this way, delayed MDPs. The planning complexity is SA though.
introduce our learning algorithm
obtain executable policy in
4.1
Regret bound
We define regret in delayed MDP
Regret(K) Σk maxxellssn. (
ViTh (st),
where ViT is the value function of the original MDP. Although the regret here is defined on the original MDP, it is equivalent to the regret of the same policy MDP aDPaug and further MDP by Proposition 3. 1. Note that we are comparing with the best executable policy. The performance degradation caused by observation delay is discussed in Section 4.2. The following theorem bounds the regret.
Theorem 4.1 (Regret bound for Delayed MDP). Suppose Assumption 2.1 holds. Let (0, be any failure probability. With probaiblity - the regret of Algorithm 2 satisfies
Regret(K) s ( (H'V TOCKK-H''S A12)
where log
SAHK and e is constant.
The proof is provided in Appendix B.I. We discuss several implications.

---

Algorithm 2 Policy learning for delayed MDPs using MDP
1: Input: Original horizon H. extended horizon Ht, policy class leeeee failure probability 7 and 27 (T, H for any t and a, data set D 0. initial policy n
2: Init: Vi++ (T)
3: for episode 1,..., K
4: Execute policy =²-1 for H steps.
5: After the episode ends, collect data D D di rh: Ai)
6: On data set Dt. compute counting numbers (sh: Ny an Sh+1) and (sh, ane dn.) = شكー 1( sh, oj = an. A = dn..
7: Estimate transition probabilities and delay distributions via
(s an) = (sp, On, 8h+1) and delay (sh, an 5n) = Σ826, (sh, ah,
(s an,
(sh, an)
Then estimators of Ph, in MDP aug is computed using ph. and dalay
8: Set bonus function as
(H A D)L
(H (HD D)c
bl an) cH
(v N (Sta Ota Sea)
N (Sta ata
for = log SAKH and e sufficiently large.
9: Run optimistic value iteration in MDP saug for H steps and obtain Th E -lexeee
end for
11:
Return: Learned policy री. for k I....,K. K.
Sharp dependence on S and A Theorem 4.1 has sharp dependence on S and A, although the expanded state space Sang has cardinality bounded by SA" Naïvely learning and planning in MDP would suffer from the exponential enlargement of AН However, we identify the sparse structures in the transition probabilities. As be seen, Ph.aug only involves one-step transitions in the original MDP and some conditionally independent delay distributions. Such structures lead to a rather easy estimation of ahg. which can be constructed from the estimators of one-step transitions in the original MDP. Meanwhile, the sparse structures make exploration in MDP aug efficient, due to many unreachable states.
Effect of the delay distribution and delay length Theorem 4. holds for arbitrary conditionally in- dependent delay distributions, even include heavy-tailed distributions. In the worst of unbounded regret. The reason this is that if the delay is
delays, Theorem 4.1 gives rise O(H' larger than H. then the corresponding state will only be observed after an episode ends and won't 't be used in planning. Therefore, we can truncate the delay H, regardless of its tail distributions.
When the maximal length of delay is bounded by < H.e.g. CDMDPs with d, = D for any h, Theorem 4.1 implies that the regret is bounded by
Regret(K) s (1)11) H3SAKL+ A12
for a constant c. A proof is provided in Appendix B.2, As can be seen, as the length of delay increases, the regret bound enlarges, reflecting the increased difficulty of long delays. Moreover, when D that is, no observation delays, the regret bound recovers that in standard MDPs.
4.2 Performance degradation of policy class ITxxe
This section devotes to quantify the performance degradation caused by delayed observations. In particular, bound the value difference between the best executable policy and the best Markov policy in a no delay environment. Recall that 1/2 is the value function of the original MDP. We denote
n nodelay = argmax, V (81)
and
Teelay = arggaaggg...m.... Fe
V (81)

---

as the best vanilla optimal policy and executable policy, respectively. The values achieved by т nodelay and deelay are denoted as Vinodde (s1) and Videlay (s1), respectively. The gap between V L.noellay and didet quantifies the performance degradation, which is denoted gap(s1) V inndelyy ($1) Vi Vi.delay (81). We bound gap in Proposition B.2 in Appendix due space limit.
In nutshell, we show that the performance degradation gap is highly relevant to the belief distribution (-1r). When (-(-(() is evenly spread, meaning that the entropy of b,, high and inferring the current unseen state is difficult, we potentially suffer from a large gap. On the contrary, when (-17) nearly deterministic, the performance degradation is small. In the special case of deterministic transitions, we have gap = O.
4.3 The (mysterious) effect of delay on the optimal value
To further understand the effect of the delay the optimal value, provide the following dichotomy, On the one hand, we show that there exists an MDP instance, such that a constant delay of steps does hurt the performance. On the other hand, in the same MDP instance, constant delay of + 1 steps suffers from a constant performance drop.
Proposition 4.2. Consider constant delayed MDPs. Fix positive integer d H. Then there exists an MDP instance such that the following two items hold simultaneously.
When delay is d, it holds that 1 Σ gap(s = O.
R
When delay is d + 1, it holds that K Σ km gap(s 1
2K log 4, with probability 1
The proof is provided in Appendix B.4. We remark that Proposition 4.2 says that observation delay can be dangerous, even with the slightest possible number of steps. The idea behind Proposition 4.2 consistent with the analysis on gap. In particular, we construct an MDP instance demonstrated in Figure 2. The reward vanishes at all times but d + 1. When delay is d, the initial state is revealed and the policy can choose the best action receive a reward. When delay is + however, there is always a 1/2 probability of missing the best action for any policy, which leads to a constant performance degradation.
d
H
41
81
81
81
81
Uniform
82
82
82
92
82
Tdi (St, 0z) for
1,2
Figure 2: MDP instance on two states with two actions. The transition is lazy until time d. Then the transition is uniform regardless of actions for time + Reward is nonzero only time d This is an example with a delay of length d causes no degradation and delay of d + causes a constant performance degradation.
RL with missing observations and regret analysis
We now switch our study MDPs with missing observations. In such environment, executable policies share the same structures as delayed MDPs, where an action is taken based on available history information. Compared delayed observations, learning with missing observations is more challenging. Since unobserved states and rewards are never revealed, we are suffering from information loss. Besides, will frequently deal with multi-step transitions, due missing observations between two consecutive visible states.
5.1 Optimistic planning with missing observations
Despite the difficulty, we present here algorithms that are efficient in learning and planning for MDPs with missing observations, We begin with an optimistic planning algorithm in Algorithm To unify the notation, we denote Sy and r 0 as missing the observation.

---

Algorithm 3 Optimistic planning for MDPs with missing observations
1: Input: Horizon H, observable rate Ay.
2: Init: 5 = θ to be all possible tabular MDPs, data set D = Ø.
3: for episode k 1, .....,.. do
4: Set policy π argmaa пax (sf).
5: Play policy x/ and collect data D U {(sh a r
h=11
6: Compute counting number (s, = Σø=ı 1 16,, = 8, a a, 8 # 0}.
7: Update confidence set
St (s,
B = 10: 00:10/(10s (1
for (h, 8, a)} n nB=-1,
S VV
where (s =
Nila,,,))) and is some constant. (g(s,))
8: end for
The majority of the algorithm resembles the typical optimistic planning Jaksch et al. [2010] but with some notable differences. In Line 4, the value function Vi,8 is for the original MDP with transition probabilities parameterized by 0. Different from the typical optimistic planning, the underlying MDP here obeys the stochastic observable model in Assumption 2.2. Therefore, the value Vi,e is the sum of all possible values under missing observations. When counting N (8, a) in Line 6, we exclude data tuples missing the next state, which inevitably slows down the learning curve. Nonetheless, the effect of missing only contributes
scaling factor in the regret.
Proposition 5.1. Suppose Assumption 2.2 holds with A known. Given a failure probability with probability 7, the regret of Algorithm 4 satisfies
Regret(K) S ([ [
VIBSAAK& AAAKKKKHHAKKK
log(1 An)
where = log SAHK and c is a constant.
The proof is provided in Appendix C.I. Proposition 5.1 is optimal in the K dependence and achieves an S²A dependence on the complexity of the underlying MDP. In the extreme case of An R O, which implies that every state and reward are hardly observable, we have Regret
δ VHASAAK) Here X is the probability observing two consecutive states for estimating the transition probabilities. Proposition 5.1 requires knowledge of observable rate Ao. This is not restrictive condition, as estimating λ from Bemoulli random variables is much easier than estimating transition probabilities.
5.2 Model-based planning using augmented MDPs
Proposition 5.1 has lenient dependence on the missing rate 1 - X2. nonetheless, is not sharp on the dependence of S. We next show that the augmented MDP approach is effective tackle missing observations, when the observable rate satisfies additional conditions. Specifically, we assume that the observable rate Å is independent of (s, a). We utilize the MDPaugg reformulation, except that redefine the transition probabilities as
Aapn(Sn+H) ac,sh) Ma (T T.)(1 An)
if ff h +
Ph. (Th+1 Thy an)
if tttt11 th
otherwise
The first case in Ph.aug corresponds to receiving the state observation time h h 1. In contrast the delayed MDPs, the transition probabilities here potentially rely multi-step transitions in the original MDP. The second case of the transition corresponds to missing the observation. We summarize the policy learning procedure in Algorithm 4 in Appendix C.2, which is similar to Algorithm 2, but with a new bonus function. The following theorem shows that Algorithm asymptotically efficient when the observable rate is relatively high.

---

Theorem 5.2. Suppose Assumption 2.2 holds with Xo 2 1 - A- for some positive constant v.
Given failure probability 7, with probability 1 7, the regret of Algorithm 4 satisfies
Regret(K) I ( [HVVAAK SAv H (+
H
where = log SAHK and è a constant.
The proof is provided in Appendix C.2. Some remarks are order.
SA rate when K is large When the number of episodes K S3(1+v)/v, the first term H*VSAK" in the regret bound dominates and attains sharp dependence on and A. How- ever, when the number of episodes are limited, the regret bound has a worse dependence on the state space size S. We also observe that as the missing rate becomes small (equivalently, v becomes large), the regret close to 0(H ASK(()).
Observable rate smaller than 1 - 1/A Theorem 5.2 holds for an observable rate Ao > 1 - 1/A The intuition behind that to fully explore all the actions when a state observation is missing takes A trials. Therefore, in expectation, we will encounter missing observation at least every A episodes as long as Ao > - 1/A. Nonetheless, when A S 1/A, the regret bound remains curiously underexplored. We conjecture that λo 1 - 1/A is critical point distinguishes unique strategies for learning and planning in MDPs with missing observations. A detailed analysis goes beyond the scope of the current paper.
Proof sketch The proof of Theorem 5.2 adapts the analysis of model-based UCBVI algorithms Azar et al. [2017]. Let m denote the maximal length of consecutive missing observations. We denote Em as the event when the maximal length consecutive missing is less than m. On event & a naive analysis leads to Ö H/poly(H) (SSA "...s*A**.. + regret, in observation to the size of the expanded state space Saug. However, our analysis circumvents the A dependence by exploiting the occurrence of consecutive missing observations is rare (Lemma C.3). On the complement of event, the regret bounded by (H - (P) Summing up the two parts and choosing a proper m yield our result.
6 Conclusion
In this paper, we have studied learning and planning impaired observability MDPs. We focus on MDPs with delayed and missing observations. Specifically, for delayed observations, we have shown an efficient VSKK) regret. For missing observations, we have provided optimistic planning algorithm achieving an O(VH352 H AK) regret. If the missing rate is relatively small, we have shown an efficient Ó ASA regret bound. Further, we have characterized the performance drop caused by impaired observability compared full observability.
Acknowledgement
The work of H. V. Poor was supported in part by a grant from the C3.ai Digital Transformation Institute. Mengdi Wang acknowledges the support by NSF grants DMS-1953686, IIS-2107304, CMMI-1653435, CPS-2312093, ONR grant 1006977, and C3.AI.
References
Alekh Agarwal and John Duchi. Distributed delayed stochastic optimization. Advances Neural Information Processing Systems, 24, 2011.
Mridul Agarwal and Vaneet Aggarwal. Blind decision making: Reinforcement learning with delayed observations. Pattern Recognition Letters, 180.176, 2021.
Shipra Agrawal and Randy Jia. Optimistic posterior sampling for reinforcement learning: worst-case regret bounds. Advances in Neural Information Processing Systems, 30. 2017.
10

---

Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for rein- forcement learning. In Proceedings of the International Conference on Machine Learning, pages 263-272. PMLR, 2017.
James L Bander and Chelsea C White III. Markov decision processes with noise-corrupted and delayed state observations. Journal of the Operational Research Sociery, 50(6);660 668, 1999.
Dimitri Bertsekas. Dynamic Programming and Optimal Control: Volume Scientific, 2012.
volume
Athena
Djallel Bouneffouf, Sohini Upadhyay, and Yasaman Khazaeni. Contextual bandit with missing rewards, arXiv preprint arXiv:2007.06366 2020.
Ronen Brafman and Moshe Tennenholtz. R-max-a general polynomial time algorithm for near- optimal reinforcement learning, Journal of Machine Learning Research, 3(Oct):213-23) 231, 2002.
DM Brooks and Cornelius T Leondes. Markov decision processes with state-information lag. Operations Research, 20(4):904 907990049777-0 1972.
Fan Chen, Yu Bai, and Song Mei. Partially observable RL with B-stability: Unified structural condition and sharp sample-efficient algorithms. arXiv preprint arXiv:2209.14990 2022.
Fan Chen, Huan Wang, Caiming Xiong, Song Mei, and Yu Bai. Lower bounds for learning in revealing POMDPs, arXiv preprint arXiv:2302.01333. 2023.
Christoph Dann and Emma Brunskill. Sample complexity of episodic fixed-horizon reinforcement learning. Advances in Neural Information Processing Systems, 28, 2015.
Christoph Dann, Lihong Li, Wei Wei, and Emma Brunskill. Policy certificates: Towards accountablc reinforcement learning. In Proceedings of the International Conference on Machine Learning. pages 1507-1516. PMLR, 2019.
Omar Darwiche Domingues, Pierre Ménard, Emilie Kaufmann, and Michal Valko. Episodic rein- forcement learning in finite mdps: Minimax lower bounds revisited. In Algorithmic Learning Theory, pages 578-598. PMLR, 2021.
Miroslav Dudik, Daniel Hsu, Satyen Kale, Nikos Karampatziakis, John Langford, Lev Reyzin, and Tong Zhang. Efficient optimal learning for contextual bandits. arXiv preprint arXiv: 106.2366 2011.
Tlamelo Emmanuel, Thabiso Maupong, Dimane Mpoeleng, Thabo Semong, Banyatsang Mphago, and Oteng Tabona. A survey on missing data in machine learning. Journal of Big Data, 8(1):1-37, 2021.
Manegueu Anne Gael, Claire Vernade, Alexandra Carpentier, and Michal Valko. Stochastic bandits with arm-dependent delays. In Proceedings of the International Conference on Machine Learning, pages 11448-3356.. PMLR, 2020.
Pedro J Garefa-Laencina, José-Luis Sancho-Gómeez, and Aníbal R Figueiras-Videe Vidal. Pattern classifica- tion with missing data: a review. Neural Computing and Applications, 19:263-282, 2010.
Benjamin Howson, Ciara Pike-Burke, and Sarah Filippi. Delayed feedback in generalised linear bandits revisited. In International Conference on Artificial Intelligence and Slatistics, pages 6095-6119 19. PMLR, 2023.
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(51): 1563-11000,, 2010. URL http://jmlr. org/ wrgg/papers/v11// http://aaaahhhaaaa html.
José M Jerez, Ignacio Molina, Pedro J Garcfa-Laencina, Emilio Alba, Nuria Ribelles, Miguel Martín, and Leonardo Franco. Missing data imputation using statistical and machine learning methods in real breast cancer problem. Artificial Intelligence in Medicine, 50(2):00-1115 2010.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael Jordan. Is Q-learning provably efficient? Advances in Neural Information Processing Systems, 31, 2018.

---

Chi Jin, Sham Kakade, Akshay Krishnamurthy, and Qinghua Liu. Sample-efficient reinforcement learning of undereomplete POMDPs. Advances in Neural Information Processing Systems, 33: 18530-18539) 2020.
Pooria Joulani, Andras Gyorgy, and Csaba Szepesvári. Online learning under delayed feedback. In Proceedings of the International Conference on Machine Learning, pages 1453-1461. PMLR, 2013.
Konstantinos V Katsikopoulos and Sascha E Engelbrecht. Markov decision processes with delays and asynchronous cost collection. IEEE Transactions on Automatic Control, 48(4):568-574, 2003.
Michael Kearns and Satinder Singh. Near-optimal reinforcement learning polynomial time.
Machine Learning, 49(2):209-255 2002.
Vikram Krishnamurthy. Partially Observed Markov Decision Processes. Cambridge University Press, 2016.
Tal Lancewicki, Shahar Segal. Tomer Koren, and Yishay Mansour. Stochastic multi- aameid bandits with unrestricted delay distributions. In Proceedings of the International Conference on Machine Learning, pages 5969-5978 5978.. PMLR, 2021.
Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
Jonathan N Lee, Alekh Agarwal, Christoph Dann, and Tong Zhang. Learning in pomdps is sample- efficient with hindsight observability. arXiv preprint arXiv:2301.138577 2023.
Roderick J Little, Ralph D' Agostino. Michael L Cohen, Kay Dickersin, Scott S Emerson, John T Farrar, Constantine Frangakis, Joseph W Hogan, Geert Molenberghs, Susan Murphy, et al. The prevention and treatment of missing data in clinical trials. New England Journal of Medicine, 367
(14):1355-1366) 1360, 2012.
Qinghua Liu, Praneeth Netrapalli, Csaba Szepesvari, and Chi Jin. Optimistic MLE-A generic model-based algorithm for partially observable sequential decision making. arXiv preprint AxXiv:2209.14997 2022.
Shichao Liu, Xiaoyu Wang, and Peter Xiaoping Liu. Impact of communication delays on secondary frequency control in an islanded microgrid. IEEE Transactions on Industrial Electronics, 62(4): 2014.
Daniel Lizotte, Lacey Gunter, Eric Laber, and Susan A Murphy. Missing data and uncertainty in batch reinforcement learning. In Advances in Neural Information Processing Systems, 2008
Christos Papadimitriou and John N Tsitsiklis. The complexity of markov decision processes. Mathematics of Operations Research, 12(3):441-400, 1987.
Pascal Poupart and Nikos Vlassis. Model-based bayesian reinforcement learning in partially ob- servable domains. In Proceedings of the International Symposium Artificial Intelligence and Mathematics, pages 1-2, 2008
Stephane Ross, Brahim Chaib-draa, and Joelle Pineau. Bayes-adaptive pomdps. Advances in Neural Information Processing Systems, 20, 2007.
Richard D Smallwood and Edward J Sondik. The optimal control of partially observable markov processes over a finite horizon. Operations Research, 21(5):1071-1088 1973.
Richard S Sutton and Andrew G Barto. Reinforcement Learning: An Introduction. MIT Press, 2018
Masatoshi Uchara, Ayush Sekhari, Jason D Lee, Nathan Kallus, and Wen Sun. Provably efficient reinforcement learning in partially observable dynamical systems. arXiv preprint arXiv:2206.12020,
2022.
Claire Vernade, Olivier Cappé, and Vianney Perchet. Stochastie bandit models for delayed conversions. arXiv preprint 17Xx:17066009 2017.
12

---

Claire Vernade, Alexandra Carpentier, Tor Lattimore, Giovanni Zappella, Beyza Ermis, and Michael Brueckner. Linear bandits with stochastic delayed feedback. In Proceedings of the International Conference on Machine Learning, pages 9712-9721. PMIR, 2020.
Martin J Wainwright. High-dimensional Statistics: A Non-asymptotic Viewpoint, volume 48, Cam- bridge University Press, 2019.
Thomas Walsh, Ali Nouri, Lihong Li, and Michael L Littman. Planning and learning in environments with delayed feedback. In Proceedings of Machine Learning: ECML 2007: 18th European Conference on Machine Learning, Warsaw, Poland, September 17-21, 2007, pages 442-453. Springer, 2007.
Tsachy Weissman, Erik Ordentlich, Gadiel Seroussi, Sergio Verdu, and Marcelo Weinberger. Inequalities for the I1 deviation of the empirical distribution. Hewlett-Packard Labs, Technical Report, 2003.
CB Winsten. Geometric distributions the theory of queues. Journal of the Royal Statistical Society: Series B (Methodological), 21(1):1-22, 1959.
Yunchang Yang, Han Zhong, Tianhao Wu, Bin Liu, Liwei Wang, and Simon S Du. A reduction-based framework for sequential decision making with delayed feedback. arXiv preprint arXiv:2302.01477, 2023.
Andrea Zanette and Emma Brunskill. Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds. In Proceedings of the Interna- tional Conference on Machine Learning, pages 7304-7312. PMLR, 2019.
Wenhao Zhan, Masatoshi Uehara, Wen Sun, and Jason Lee. PAC reinforcement learning for predictive state representations. arXiv preprint (tt:::2200005335 2022.
Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Almost optimal model-free reinforcement learning via reference-advantage decomposition. Advances in Neural Information Processing Systems, 33: 15198-15207, 2020.
Han Zhong, Wei Xiong, Sirui Zheng, Liwei Wang, Zhaoran Wang, Zhuoran Yang, and Tong Zhang. A posterior sampling framework for interactive decision making. arXiv preprint 1xxx:2211.01990 2022.
13

---

A Omitted proof in Section 3
A.1 Proof of Proposition 3.1
Proof. Consider an arbitrary fixed inter-arrival pattern Ao. , AH-1- We show that the ex- pected accumulated rewards under this inter-arrival pattern are identical for MDP aug and MDP aug. In
MDP aug. we have
E
ang ( (Th, an) Fi. ........, An-
h=1
H
(x)
E
ang (St arp 11fer = 031(th E , H3} TI, To, Ao....... A
h=1
H
(5z)
EE
(88:: an)
TI, nr..o..., An-1
Th (Th, an)
Do....... An-1
TI, Do.
where equality (z) invokes the definition of ang and equality (ii) eliminates zero reward terms. Now taking expectation over all possible inter-arrival patterns, deduce
11
E
Fang (Th, and
EE
ahg (8h, an)
The proof is complete.
B Omitted proofs in Section 4
B.1 Proof of Theorem 4.1
Proof. We adapt the main steps from Azar et al. [2017] for proving the theorem. The proof consists of verifying valid optimism and developing regret analysis. We denote Q as the optimal Q-function for MDP aug. When analyzing the regret, we also denote @h as the optimal Q-function in the k-th episode.
Valid optimism To begin with, verify that the choice of the bonus functions leads valid optimism in the following lemma.
Lemma B.I. Given any failure probability 7 < 1, we set a bonus as
(v
Hi
Hi
(Te, on) caH
No,, (St. Otn Se,) V No. (Sta Otn
where log SAHK and CA is constant. Then with probability 1 7, it holds
Th. (Th, an)
Q aug (Th, an),
Vha (Th) 2 Vi. for any (k, h, Th, ax)-
Proof of Lemma B.I. We compute the cardinality of the expanded state space Sang as
H HSA
4 "+ H+
HS
A-1 2HSA"
Sang
2=0
For fixed episode k. we show by backward induction that the assertion Lemma holds. To case the presentation, omit all superscripts k all subscripts "aug". well as the tilde - notation.
14

---

When h = H + 1, the base assertion holds immediately. Suppose the assertion is true for time h + 1. At time h, for any fixed (Th, an), (T an) H. the assertion holds true. Otherwise, we have
Qn (Th. ah) (%, an) 1P% 7++1((TA an) [PAV Il(TT an) by (Th, an))
z PPh PaoV (Th. an) b/ (Th,
(A)
We show lower bound on (A). If 2 H, expanding the transition kernel Ph. leads
(A) = Σ (T+ (T an) - Ph an))
Th+1
Vh+1 (T+x(Th+1)(a (8t, at.,) Pt, (8e, +1 +1/8 (th))
+1
(1)) CA,1HH
H
Nea (St asy
where equality (i) requires Th++1 to take +6,+1 11 as the new state observation, and inequality (it) follows from the Hoeffding's inequality (Lemma D.2) with a constant CA,1. Note that the Hi term in the numerator comes from union bound over Saug x A.
On the other hand, if h < H, expanding the transition kernel Ph yields
(A) Σ Vi+ (T (Pr (Th+ 1/7, an) - pn (T144 un)) Th+1
Vht (Th+1) (P (7 an) - Ph Pra(Tt1lTaa an)) 16 = (1h+1 = ia + +1
Th+1
(Ai)
Σ (ita(Te+a)) (Te4aa an) - Ph (h an)) (6ent1 = Ec, + +111fl++1 = 1,) Th+1
(Aa)
Note that (Ai) accounts for receiving new state observation in Th+ and (A2) accounts for no new state observation. We tackle these two terms separately. For (A1), we have
(A1)
Σ (T+i(Th+1) ((1 -00, (Sta Oeny St DiPr, (St 180,, ae,)) )- 1(1--111--1 Oea. (sen, ae,, de,, })pe, (Sea 18t0 asn))
81p-1
Σ (Tta) ((1- Ōrg, (Ben aen Sen)) (1 Orn, (sey, aan )ex))) Des. (Ben I 18ta Oen)
Σ (T+:(T1)))11 Ozn (sen, , aen, )e (Den (Sea 1880 asn)) ) - Pea. (Sen 18en (ew))
H
2 - H 00, (Sta Utn, Sea) Oz, (Sta, Otg Sen) CA.2H V
Ne, (St, at,))"
where in (i), the first term is the estimation error of 1 using the collected data, the second term follows from Hoeffding's 's inequality, and C4,2 is an absolute constant, For (A2), we have
(A2) 2 H 0r., (S an, Se,)) br, (112, aes Sea
since Th+1 is now uniquely determined. Summing up (A1) and (A2), we obtain
Hu
(A) = (Ai) + (A2) 2 -2H Ör, (St,, ae, de.,) - Or,, (St,, ar dem)) ca,HH Ne, (8t at
15

---

It remains to bound the estimation error of de, (st,, ams S.,). Using the Hoeffding's 's inequality again, we obtain
Deg (s aen den) Pen (stn aen den)| S coV No. (St aiy dea.
H
Taking сд max/cA,1, CA,2, co. 2), have
H (A) -CAH (V (Nn Oen Sta)
He No, (Sta aea)
V
With the choice of the bonus function, can be checked that
@ (Th, 0n) Sh aug (Th, an) 2 (A) + (Th, ax) 20
with probability 1- 7 for any an.)
Regret analysis In the sequel, we omit subscripts "aug" and tilde - for simplicity. Thanks to Lemma B.1, we consider (Qh - Qh (Th axt) as upper bound of (Q% 0% (Th af).. We
bound (Qh 0%) (Th a%) by
(0): - 0% (Th, ah))
(PAVEL h+1 Pr ( (Th a + (Th a/
(PM Pu]Vi+1) (Th a + (Pp) PAIlV - (Th at)
(PA[Vit+ vi++1)) (Th o b% (Tr, a
PPA - PAllV - Vittl) (Th a + (PM[V v (Th, ah) + (T at). (B.1)
(A)
Similar to Lemma B.1, for h > H, we expand term (A) into
(A) Σ (Ph aft.) pa (Th+1llT at)) [V Vitti(T442)
-EV+ V (pt, (8th atr.) Pt, (8t a,,))
(B.2)
#ta+1
On the other hand, for < H. the decomposition of term (A) is more complicated. We have
(A) Σ (Th at) (m( IT a) [V/t+ V
Th+1
Σ M Vi4zl(TA+1) (T++ a Pn (m(Tutil8s,ttt) at)) 16 = (1++1 = 1 + 1]
Thi11
(A1)
V Wit (iTT4() (pt (Ph(Ta
a Pn (T 1r ati) 166mm1 = 6,4 + 1}1(tn+1 = =t/
Th+
(Aa)
Term (Ag) can be directly bounded by
(A2) & H 00, (st, at, 8t, Or, (st, at
H4
S coll, V
N (st at 8%
16

---

with probability 1 - To bound (A1), we have
(A1)= E | Vitza(Tn+11) ( (1-0% (sh, atn oth)) Din (8tn 18t1
(1-07
#en+1
Ocg (1-0s, (5t ais 5th peu (0en) :
Σ [Vit1 Vittal(T+ta) ((1- (5 abs .g%)) (1 Osn (shn al, 8%r Pin 1s abb
+ Σ I Vh+ (e (st ai )) (pt, (stnts 1st, alr Pen. (8tat 1ot at
- Osn (oin, Oin
o(h))
E 1 Vi+tI(TT+1) (Pt, (Staer a )- Pen (Sents lo alr))
81a11
+ H Ol (st O2s
st.,)
Pen (st aft 5tt
$ (1 BB, (st,, Oin st.,
Σ V Vitil(Tatl (Pt, (sterr 1 a Pen (Stnes 1st att
11a11
He NK. (sh at
+ coHH V
8%
Putting (A1) and (A2) together, we obtain
(A) (1 - -2, a 8),))
DIV= Vi++a(( (Pt, (Sthn Ish, Pta (Se (stnts o)
9*p+1
Hi NE (st at, 8t,))
20gll V
(B.3)
In both (B.2) and (B.3) for different ranges of h, we apply the Bernstein inequality (Lemma D.1) to derive
Σ
Iv W++1 (i (Pt,, (Sea+) 1st, of Pen. (s 1st af,)))
#1441
Peu (8tn111 1oh al
Se.
Σ V++ (i++l((a+1))
4 Nk. (sfi, a
No. (st al,))
(4)
Pia (Strra (st, An
(2cH + 1)e
c. Σ
[ h+1 ((
2cH
Ni (st abw)
91g-1
cc
SH(2cH + 1)
+
1
Σ |v Vi (Stn4s 1st ofi.) #th+1
(B.4)
NK N
(5) ob.))
2cHl
where inequality (i) follows from Va < a aa+b b. Substituting (B.4) into (B.2), for h 2 H, we deduce
1 Σ
Vh Vi (T (Se lst at,)) + cSH + 1)x
(A) S 2H
NJ. (st at
S1111
(6)
mSH2
(PA[V vial (Th, a + d'
2H
NÀ. (s) at,
where c' is sufficiently large constant. By the same reasoning, substituting (B.4) into (B.3), for H, we have
(A) S 2H
1
(1 Oc,, (st ai 8t,))
Σ [ Vital(TAt1 )rr,
cSH(2cH + +) N (sfi al,))
Sent1
17

---

H Nt. (ot, aii 8
20gH V
(
SH Nł, (sf, at,))
He NĖ, (sf,
(Pn[vit1 - Vitill (Th ant d
+ 200 H
2H
of 8%
We denote ch c' Ni, (s "
SH
Now we have unified upper bound on (A) for any h E [1. H as
1
He
(A) - (PalV h+1 vi++l) (rh a c% 20oH H,
2H
V
No. (ol ai, oth)
(B.5)
Substituting (B.5) back into (B.1), we have
(V/+ v/th) (r+) (0h Q%:
(Th att)
H (Ph [V vi=+)) (Th ah) + ch + 26h + 2coHl / No. (s ai, 8%,
1 + 211
We further denote ex = (Ph [v/ v (Th a - [vi+1 - vh+il (Th+1) and rewrite (V% vi** (r as
1
Hc ([V villl (Ti+1) + <h) + ch 26% + 200H V N (5% ah 8t
(V/ ViTh (Th)
2H
Recall H 2H. Using recursive summation argument, we deduce
h
Hi NK. (st at 85
(V/ - ViTh
1
ch + ch + 25t + 2 V
2H
h=1
2H
Hc
Sh
ch 26 + 20al1 v
NB, (st.. ofi 8%,
As consequence, the total regret is bounded by
He
Regret(K) Se
<k
+ că 2b% + 2
(B.6)
NK. by.
(st. at 8t.))
We need to sum over ck ck by. Consider ch first. We have Sh
SH
N (st at,))
K
H
SH2
N (5t a
b=1h=1
SH A2
(B.7)
where inequality (i) invokes the fact that 4, only takes value in (1...., H) and each N (st, a repeated at most times, and inequality (ii) follows from the pigeon-hol hole argument in Azar et al. [2017].
Next bound the summation over t/. This is martingale difference sequence. We apply Azuma- Hoeffding's 's inequality (Lemma D.3) with n = 2H and C; = 4H to obtain
K
2H
Σ
< @VVK44
(B.8)
A
hm
18

---

The additional H dependence above comes from union bound over Suug x A. Lastly, we tackle the summation over bonus functions b/. We have
H aes)
CAH
N
(Sth
h=1
K H
Hr NE. (Sta 98a)
CAHH
1m
S
c &
(B.9)
Putting (B.7), (B.8) and (B.9) together, we deduce
2H
Regret(K) c (H A VH*KK)) + 2eca H
Σ
H
N (s at 8k
k= hm
for some constant To this end, the only remaining task is to find Σ Σ 2H which undergoes similar argument as the bonus summation. We have
-i=l
No. (et, ot
H
Nà (s 2
8t
N ( aj 8%)
N (x.0,5)
H Σ
(h,
2H Σ Σ (s,
(h,9,a)
(1)
x 2H
VSAKH
(18) 2H SAKK
(B.
where inequality (1) invokes Σi= 1/v1 < 2/n, inequality (di) follows from Cauchy-Schward and inequality (iii) uses the fact that bounded by Plugging (B.10) into the regret bound, we obtain the desired result
Regret < (H.VSAK H A + VHAKI
with probability 1 1- Absorbing V H into H H* VSAKi yields the bound in Theorem 4.1.
B.2 Regret under bounded delay
To obtain the regret bound under bounded delay, we only need to modify several steps in the proof of Theorem 1. Specifically, in Lemma B.I, we replace I by D + in the square root, so that the bonus function becomes
(T., an) = CAH (V/
(D 13e No, (St,, aea Sc.) +1 Ni, (Sta dea)
/
(D+ 1)c
The optimism still holds, since the expanded state space contains at most historical actions.
The second modification is to observe that since the delay is bounded by D, each counting number N only repeats at most D + times. this way, (B.7) becomes
K 2H
ΣΣ
c <
cc 1) A22 A.2.
Jum Am
19

---

(B.8) and (B.9) are replaced by
K 24
2H S HASSAK
() - 1)H3% and
S
k= =1
k= 1=1
respectively, Lastly, we also have
K 2H
(tt oft 8t,)
Putting these updated upper bounds together and substituting into Regret(K), we deduce Regret(K) S (
2 A22)
B.3 Statement and proof of Proposition B.2 Proposition B.2. the setup of Section 4.2, we have
gap(s1) S Σ J. ((anexttt) a)]
max Eg (ar (ph
zaain mandelny (r)
Ph
+ 2 Iph Fiodellay
Ph
ITV
where Ph.
Toodelay and Ph.
Tidlay are visitation measures induced by "nodelay and Tdelay respectively.
Term E₁ is strictly larger than zero due to the convexity the max operation. Term &g accounts for the difference in the visitation measure. When the original MDP has deterministic transitions, we can check that ε is zero, since the expectation over concentrated on a singleton that be inferred from history. Hence, the visitation measures V Loudelyy (81) - Vi,dlay (81) = O. On the contrary, when bx(-17) is evenly spread, meaning that the entropy of b, is high, we potentially suffer from a large performance drop, in that, inferring the current state is difficult.
also identical, which implies
Proof of Proposition B.2. Let T1, TI,...,TH TH denote the states observed in the delayed environment. Since Th nodelay is greedy and Markov, obtain
V nudelly (81) = R.T nodelay
(n(sn, (a(s,,a))a)
+ E uodelay (M(r
modellyy
Σ Ta((snan)l an))si
E Fuddelay
Σ (s( maxrn(s
Recursively applying the above argument, deduce
Vi modelay (s1) E Fooietas
ΣΣ
(n(s) maxra
1=1
We also rewrite V Vi.delay ($1) as
VT,delay (s1) dalayy
(h(sh as)
+ danlyy [Sr an [r)/sslssl
dastay
Σ (s,s,, an)(s1
+ Thilay
max
bu bu(s(TH)r((s.a)s
a
20

---

dalla
Σ max Dmn(staaralssa)))
Then we write the difference between Vi, nodelly (81) and Vi (81) as V Lnodelaa (81) - delayy (s1)
max by (s)))r Tandalay (r)
max Σ bn(s)7)ra(s,a)))
daalay (r)
H
max by (s/7)) a) Juudelay (r)dT - max Σ ba(s|r)ra(s, P) Fnodeler (T)
h=1
max Σ (s(T)) (s) Soddlayr (T)dT- max Σ bb((st)rrnsss0)pp
Tdeiar (T)
H1
Σ
(ESDba (Eonoa(i)) max max Ph
Fundiior (r) 2 -hh 1|TV
Fnodelar Tioloy
4=1
We also have
V L.ndellay ($1) - Vi,aalay (81)
max by (s)))))) moddlly (T) 1 max by (s)T)r( a)pr
Σ
Kaalay (r)
Σ max bn (s) a)ph Taeter (r)dT= max Σ ba(s)))r a)h
Faster (r)dT
Σ [/ [max (n max m. Ph
11
Taolay (r)dT + 2/ Roodelay
Ph
Rdeloy
1
hm1
Combining the above two inequalities, we obtain
V Vinnddelay ($1) - (i,delay
Eonda (Bonbscilllaarr((ss)] max E (inoa (p
Taster A Ph
Tandelar (T)
1=1
211ph
modelay
Ph
Tialay
lrv
The proof is complete.
B.4 Proof of Proposition 4.2
Proof. We construct an MDP instance (S, A, H, Ri P) for H > d as follows. Let = {1, and A = {21, For the reward function, we have
(n a) = [1
a a, and = +1
0 otherwise
The reward is nonzero only at time d + 1. The transition probabilities are defined as
1
if d
(s 8, a) =
if + d and s' 8.
0
otherwise
21

---

The transition probability at step d + 1 says that s' is uniform regardless of the previous state and action. Suppose uniform initial distribution on 81. We first show that if the constant delay equals then there exists policy n achieving maximal value. Indeed, the policy is chosen
dan (Uniform(A)
if d + 1 if + d + 1.
Th d. a -h-dhh-))
is straightforward to check that x is optimal, since at step + 1, $1 is revealed and the policy takes the optimal action ds₁ obtain reward 1.
On the other hand, if the constant delay equals + 1, then any policy suffers from constant performance degradation. To see this, in a single trajectory, since the starting state is only revealed at time d 2, the policy at time + 1 cannot exploit the information of the initial state. Therefore, any policy coincides with the best action with probability 2. For K episodes, with probability 7, the total reward of any policy π E Hexee is bounded by
K log ?
Σ v S
2
K
+
due to Hoeffding's inequality. As a result, the performance drop is at least
gap(K)> 2 2
>
2K
log -.
C Omitted proofs in Section 5
C.1 Proof of Proposition 5.1
Proof. We first show that the ground-truth transition probabilities P% belongs to B& with high probability. By Theorem 2.2 in Weissman et al. [2003] (see also Equation (44) in Jaksch et al. [2010]),
the k-th episode, for any fixed (8, a, h), we have
(s.
(1Px a) ph. (-1s, a)r 2t) s -2 exp
2
Setting & = V/ (F(a,)) for some constant c. ensures that
St (Pt( ph (-1s, S V (s,
holds over any (s, a, N, k)) with probability y. consequence, the event pf (-18,0) e B* holds with probability 7 over all (s, a, h, k).
Conditioned on the high probability event pf," E B for all (h, s, a), we have by standard performance difference arguments that
ViJ (s1) Vg. (s+)
Vaa (s
vz²((tt) (sf)
max Elllosee
K
H1
68
Egy (((PR* - (-10)) an). Vo (+))
h=1
K
H2SL A H (s an)
Bg"
H
H
HVHHK
N ( at)
1
22

---

(ie)
log HK
d
VH'S SAHK + VH*KI
log(1 2g)
1 log(1 x
<3
VHASTAKE VHIKI
where inequality (i) follows from the valid optimism since Line 4 in Algorithm is taken over double maximization, equality (ii) recursively expands the value function and (-.-) denotes the inner product. inequality (iit) invokes Azuma-Hoeffding inequality, and inequality (ic) invokes Lemma C.2. C
C.2 Algorithm and proof of Theorem 5.2
Algorithm 4 Policy learning for MDPs with missing observations
1: Input: Horizon H.
2: Init: ( 0 and Qu(T, a) H for any T, a, data set D = 0. initial policy x²,
3: for episode k =1-1,... 1..... do
4: Execute policy -=-1
5: After the episode ends, collect data D D U {(5) og r/))
6: On data set D* compute counting numbers
(TA, an)
Σ 16 The a = ah, sht # 0} and
Ny, = Σ
1 10% = 0}.
==1
7: Estimate transition probabilities and delay distributions via
(TH, ah, 8h+1) No (Th, an)
( ax)
and X = Nhi/k.
8: Set bonus function as
Hc cH (v N
(V + +V
for = log SAKH and e sufficiently large.
9: Run optimistic value iteration in MDP MDPsug sug for H steps and obtain T² Iexeec
10: end for
Return: Learned policy t for I....,K. K.
We remark that similar to delayed MDPs, in Line 9 the planning is on MDP aug and the obtained policy executable given any E Sang when state observation is missed. Therefore, the planning complexity is SA" Different from Algorithm 2, the bonus function here depends on multi-step transitions, in that missing observations are permanently lost.
Proof of Theorem 5.2. The proof utilizes similar steps as Theorem 4.1, with extra the summation of bonus functions.
Valid optimism We verify the choice of bonus functions leads a valid optimism.
Lemma C.1. Given any failure probability 7 < we set bonus functions as
Hi (T, an) = cH (v NV(n + V with == log
SSHHK
Then with probability 1 - 7, it holds
Di (Th. an) 2 Q (0h.nu(TT an), Vhh (Th) > (TT) for any (h,
23

---

Proof of Lemma C.I. In the proof, we omit subscript "aug" for simplicity. We use backward induction on time again. The base case of + holds immediately due to the initial value of + Suppose at time h + 1, the assertion holds. Then for time h, if Qh. H, the assertion holds trivially. Otherwise, we have
Qu(Tn, an) QT(T,, an))
fn(T,, an) + [PA Vi an) - Th an) [PA V (T an) + b9 (Th, ah)
PPr PalVi++1 (Th, an) + FT((Th on) rh (Th, an) + by (Th. an).
(A)
(B)
We lower bound (A) and (B) separately. For term (A), we have
(A) = Σ Vitti (T as) Ps (T an))
Th+1
Σ
Vit (T++))))) (Ph 04) (m an)) ( lftn+1
= h h 1}
Th11
Σ Viet (Th+2) (T+4111) on) ( an)) 1 (th+1 =th
Σ (T+a() (1- PN (8141181 acmin) - (1 - An)pa(9RtilBen agsihh)
#h+1
(A1)
Vi41 Mrn An)-
(12)
In (A1), Thot is 1. We bound (Ai) as
(A1) Σ Vi+n((n+1)
Xn (sh- 118- ae, (1 Au Ma (8h+1 aench))
#6+1
+ (1 - (sn+il011 accs)) - (1 Andrn (#n+1 1sc,, aswchh)
Σ (itt(Ta+1)(11 - And (f1 aessh) ph (n((411//0 (en, a(a)t))
8611
+
Vi (TH4)))))) - Aw (sn at.sh)
8h+1
Nr Anl.
-CAH Nu(Th, an)
where inequality (i) invokes Hoeffding's 's inequality and holds with probability 1 - for any The and some constant CA. Term (A2) is immediately bounded by
(Aa)
5 An
Putting (Ai) and (A2) together, we derive
(A) 2 CAH
Hb.
2H 5nn An
Na(Th.
with high probabilty. For term (B), we have
(B) = Σ r(sn, an) (bu(salTh) - ((((l)))) 2 -CBV
H NT((T.
8h

---

Taking ca + cB and summing up (4) and (B), we have
Qu(Th, (T, an) 2 cH (T(TT. an) 2H |5n
He
in| + by (Tr. an).
We estimate X by its empirical average. In episode k 2 1. we have access to i.i.d realizations of Bernoulli random variable with rate A (observable or not). Therefore, by Hoeffding's inequality, we have
log
HK k:
C E
An S
21
2
Substituting into (T,, an) 17 (Th; an) and reloading constant give rise
an) -cH (V (Ta,
(T, on) - (T..
He
L
+
b% (Th, ap) 2 0.
The proof is complete.
Regret analysis We omit subscript "aug" to ease the presentation. The same derivation in the proof of Theorem 4.1 gives rise
(Q% - Q2, (T) at) = (2 - Q7. (T) a
$ (PA - Pu]lV/+1 - Vittl) (rh a + (PM V Vital) (TA, ah) + (th ah)- (C.1)
(A)
Lemma C.I shows that (A) can be written as
(A)
Σ M (ital(T An) (7h (0n at..w) pn (on+11l0 :
8111
Σ [ Vi 11 (sn+ al
8h41
M4+1 (i - )x) (P (sn+alls at..th ph (80+1 af + H 15A An
8h41
Σ [ V(++a((T+1)) (7% (sp+ 1o, alw.n) (n afrch) + 2H _
(1 >
Following the derivation in (B.4), (B.5) and (B.6), we have
K
H
ch + c + 26 + 2H /
Regret(K) S
1=1 h=1
(ch ch + 2bb)) 2V H4
h=1
where <x = (Pr [VA
v.*
(T
a
VWt1]] (Th+2) is the martingale difference and [v/
tt = c' S
N.G
Counting number summation inequality, we have
The summation over < is standard. Using the Azuma-Hoefiding's
K
sk S SeVKH4.
Am 1 Pamm
25

---

It remains to find the summations involving (T a.) First, we show that the event &m {h tp S m). i... the maximal consecutive delay is upper bounded by m 0, holds with high probability. We have
P(Em) - (1 H(1 Ao) A0)== K
since A is a uniform lower bound of Aς. Next, we provide an upper bound on N (Th. an). For given tuple (h, The ag ts), the consecutive missing length is h - ty 1. Such missing pattern appears with probability at most (1 >o >o) As consequence, denote C -1 as the number of h - in consecutive missings in K episodes. With probability 1 7,, we have
CK -h S K(1 - (o) 10) --)"-~=-144 V K(1 ba) H
by Bernstein's 's inequality in Lemma D.1. Furthermore, at a fixed time h. we use Lemma C.3 to bound the gap between two consecutive appearances of the same missing pattern. We instantiate Lemma C.3 with 0 (1- (1) A0) --- and obtain that the gap is bounded by -1o with probability 7. Within the gap, the number of consecutive delays of length larger than h 1 bounded by
C2n-ta-1 log(1 - (1 (a) (1 - 200
1.
(1 - Ao)m-en (1-A0) H +
log(1 (1 Xo) vn 11)
(i8)
2((1 Ao) Hi + 2(1 Ao) + L,
where inequality (i) follows from Bernstein's inequality again and inequality (it) invokes the fact x + log(1 x) S 0 for x E [0, 1) and bounds [x] by x + 1. Now we can bound the summation of the counting numbers. Conditioned the event Em, we have
K
H
N (r.o)
O2h-tz-1 -1
Σ
V
(h,T,a,ta)
S 2 - 22(11-))) + 2(1 - 1o) (1)
Σ (NK(T.
(h,T,o,th)
(8)
< 2 (V2(1 2o) He + 2(1 -Ao) +1) Σ
KK
Ch
h.th
22 (V2(1- - 2o) + +211 - 20) +1)
Σ V
SA (x)(--)0)))---11 + A K(AP(L (1 -1 Ah-la-14
h.
(di))
2(22(1 Ao) + 2(1 - -o0) Σ SSA
(SA(K++ (K VKAKHKA Am)) AA
2
h.th
22 2221 Ao) + + - d0)+1 H²
SA (KKKKK"HH+ A
2 H (K VK Hi Am)).
where inequality (i) follows since N is repeated most C2h-6,-1 times before getting an up- date and inequality (ii) follows from Cauchy-Schwan inequality, and inequality (idi) invokes the assumption of XA < 1. Moreover, conditioned on the event &n, we also have
K
h
N (T.a)
& Σ C2
Σ
-=
(h.r.atta)
26

---

(12(11 Ao) + 2(1 1(1-10)+1) +1)
Σ (h.r,att))
log (T,
2 1H!225A log
Combining the above
On event &m, the regret is bounded by
Regret(K) (1)
SH NE o
Hi
VHIK&+
ΣΣ
+
HH
( at))
k=1k=1
ATh HI
A K
c H² SA
[1
+
+ AT + VH*Kk
K
where e is a sufficiently large constant and we substitute the bonus functions into inequality (i). On the complement of E. the regret is bounded by (11- ((E))) )) - H² (1-1))))) - We choose such that H(1 - P(E.)) - H² - Ao) Σ HRVK. We can now check
log K log Ao
m
that A exp
log log(1
Ao log v K
< K 2,ोo,. Therefore, combining the regret on event E.n.
and the complement event cf leads
Regret(K) S H H.VSAKK S2y HOK
The proof is complete.
C.3 Supporting lemmas
Lemma C.2. Suppose Assumption 2.2 holds. With probability 1 for some failure probability
Y > O, we have
log HK
VSAKH.
log(1 XR)
(5 at)
h=
Proof of Lemma C.2. For any time ht we denote (Ceff(( (h) as the collection of episodes that the l-th and (h + 1)-th step observations are available. It is clear that the cardinality of KCfff (h) is bounded by K for any h. Within each xceff (h), we would like to bound the gap between two observations. Thanks to Lemma C.3, the gap is bounded by with probability 1 K (1 1z We set
log
K(1 - 13) = 7/H, H, which implies
Therefore, for any time step h, available
Tox(1 X55
observations are most separated by g episodes.
With these notations, we bound
log HK
Σ
Σ
NK (s) a
log - 2g)
4=1 kEKalf (M) N
log HK
H K
log( 1 - X2)
h=1 A= Nh at)
(xie) 2
log HK
VSAHK,
log(1 - X3)
where inequality (i) follows since N₁ will only be updated when h e KCfff and then repeat at
most
log lo x
FK
times, inequality (ii) invokes the cardinality bound of KCefl (h), and inequality
(iii) follows from the standard pigeon-hol principle.
27

---

Lemma C.3. Let {u,)/- be ii.d. Bernoulli random variables. Suppose P(u; 1) 8. Define the largest gap between U, 's as
g(k) suplj - i: u, 0 and u 0 with uy for - - 1.....j 1}.
Then for any integer q > 0, the following tail probability bound holds
P(g(k) > 9) S kgot!
Proof of Lemma C.3. We denote Ineg = {l....., Lm} as the index set for = 0 when = 1,..., negl Let U2 f++1 lg. which a geometric random variable with success 0. Note that the cardinality of nueg is at most k. Therefore, we have
P(g(k) > g) S P max Vj > ②)
=I....
1 P P(U q for 1, .....
= 1 1 - 1 (1-0st2)*
k
I 188t1
where the last inequality follows from kg0+1
S (1 (1-80+1)4
D Helper concentration inequalities
Lemma D.1 (Bernstein's 's inequality). Let Z1,.... be i.i.d. zero mean random variables. Suppose bxd S M for any ,,...,Tu. n. Then for all positive it holds
s exp (-E
1
P
Σ D >t
Eatt
Σ
Var(z:] + Mt
In particular, given failure probability y < 1, it holds
Mlog log 1
P
Σ
Var[z:]] log + M
5.
Proof of Lemma D.I. The proof of Bernstein's 's inequality is standard, see example [Wainwright,
112
2019, Section 2.1]. Here we verify the second claim. Let exp E" Var(x.1-3Mi S 7 hold true.
We find a suitable t by
112
exp
S
D Var
[D.]]
+ +gMt
12
2 log
Var [x:] + M
?
1
1 7
LM log
2
Var [x:] log
7
1 1
[
log
M2 log
2
+ M log 7
7 g
is enough choose t
Σ Varlzy log M log 4.
Lemma D.2 (Hoeffding's inequality). Let #1, I. be i.i.d. random variables. Suppose a; S S b, for any = L,..., n. Then for all positive ł, it holds
212
Σ
T3
E
Σ
S 2exp
Σm (be - a,)2
28

---

In particular, given a failure probability < 1, it holds
Ei=
(b) 0,) log 2 7 5%
P
E
zz
n
2n
Proof of Lemma D.2. The proof is standard; see [Wainwright, 2019, Section 2.1].
Lemma D.3 (Azuma-Hoeffding inequality). Let æ1. 2n be martingale adapted to filtration
Fi C... C Fa. Suppose E|2; F[ = 0 and aag E E(r:]] I Cs. Then for all positive t, it holds
12 (- o
Σ
x;
[0 > t S exp
particular, given a failure probability 7 < 1, it holds
1
Σ
x.
E B(xg]
log
S:.
Proof of Lemma D.3. The proof is standard and applies Lemma D.2.
29


Reviews:
[{"review_id": "YM9YqES8Ir", "reviewer": "Reviewer_yWj8", "summary": "This paper studies reinforcement learning in the setting where MDP is with delayed state information, but delayed observations still arrive in order, and in the setting where the state information of MDPs could be missed and never be observed. For both settings, this paper provides provably efficient RL algorithms with sub-linear regrets, whose dependencies on the number of episodes are optimal. In the setting with delayed state information, this paper shows the impact of delay $d_h$ on the performance of the optimal policy. In the setting with missing state information, this paper shows the impact of observation rate $\\lambda_h$ on the regret. The results seem interesting to me.", "questions": "1. Why is the regret in Theorem 4.1 for delayed state information independent of delay? Is it because the optimal policy also suffers from the delay? Intuitively, the performance of the online policy with larger delay should be worse. For example, should we hope much better regret in the case with no delay than the case with infinite delay?\n\n2. Even though when the delay $d_h$ is 0, there is still a gap in the regret in Theorem 4.1? Could you give some insights whether this can actually be sharpened or why is this true?\n\n3. Similarly, in section 5 with missing state information, even when the missing rate is 0, the regret seems to keep to be larger than the best regret that could be obtained?\n\n4. Above line 119, the executable policy class is defined based on the action sequence. However, based on the notation, the action is always known, why the action sequence $a_{t_h:h-1}$ is important there?", "limitations": "Please see weakness and questions above.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. This paper studies MDPs with delayed state information and MDPs with missing state information, which seems to be an important problem.\n\n2. This paper provides algorithms for these two settings, and proves the regret guarantees.\n\n3. This paper shows the impacts of the values of delays and observation rates on the performance of the policies for learning in MDPs with impaired observability.", "weaknesses": "1. The novelty of the proposed algorithms is not clear to me. For example, algorithm 2 seems to be a simple application of the tabular RL algorithm to the case with delayed state information?\n\n2. It is not clear for me how to understand the regret. For example, why the benchmark in the regret is the optimal policy with impaired observability? Is it more reasonable to compare with stronger optimal policy, e.g., one with full observability? Since if the optimal policy is also with impaired observability, why is the problem more challenging?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments!\n\n>**Q1**: Novelty of the proposed algorithms.\n\n**A1**: A naive application of tabular RL algorithm to our problem would yield exponential $\\tilde{\\mathcal{O}}({\\rm poly}(H) \\sqrt{SA^HK})$ regret. We are able to achieve regret that scales with $\\sqrt{S A}$ by utilizing structures of the delayed MDP and novel construction on bonus functions.\n\n1). To tackle the exponentially large state space in the augmented MDP, we construct a reformation tilde_MDP_aug with past reward and an extended horizon. This new reformulation provably attains the same expected reward as MDP_aug and serves as the basis of Algorithm 2.\n\n2). In Algorithm 2, we provide a novel construction on the bonus function to ensure optimism with high probability. The intriguing fact of the bonus function is that it is akin to the bonus of UCBVI applied to the original MDP. However, this is a consequence of our analysis exploiting the sparse structure in the transition. A direct application of the UCBVI algorithm to tilde_MDP_aug will easily end up with annoying $N(s_{t_h}, a_{t_h:h-1})$ counting numbers, which leads to exponential regret. In addition, we also provide uncertainty quantification on the arbitrary delay distribution, which to our knowledge is never done in prior work.\n\n>**Q2**: How to understand the regret.\n\n**A2**: Our theory provides comparisons to both the best executable policies and the even stronger full-observability optimal policies, where the former is termed as regret (Line 204) and the latter is termed as gap (Line 232-233). Briefly speaking, regret measures the learnability of the best executable policy and the gap characterizes the unavoidable performance degradation due to impaired observability.\n \nIn our separation theory (Proposition 4.2), we have shown that the gap is heavily instance-dependent and can be large in the worst case.  We also provided a general bound on the performance gap in Proposition B.2, which is deferred to appendix due to space limit. In the worst case, there is a constant gap compared to the optimal policy without impaired observability, indicating the divergence of the gap as $K$ increases.\n\nOn the other hand, even compared to the optimal executable policy, as mentioned in the introduction, naive approaches easily result in an exponential regret. Our algorithm and analysis led to the first **tractable** solution to RL with impaired observability, i.e., achieving complexity that scales polynomially with $S$ and $A$.\n\n>**Q3**: Regret in Theorem 4.1 independent of delay?\n\n**A3**: We do not assume any distribution on the length of delay. Hence, the regret bound holds for arbitrary delay in the worst case. The idea is that we consider finite-horizon MDPs, therefore, we can truncate the length of delay at $H$ (Line 221-225).\n\nWhen the delay is much better behaved, e.g., is bounded by some constant $D_{\\max}$ smaller than $H$, we can obtain better regret bounds. With the same algorithm, a very slight modification on our proof leads to a regret of $\\tilde{\\mathcal{O}}((D_{\\max}+1)^{3/2} H^{5/2} \\sqrt{SAK})$. As can be seen, when $D_{\\max}$ is small, the regret becomes small. Moreover, when $D_{\\max} = 0$, i.e., there is no delay, the regret recovers that in standard MDPs without delay. (Technical details of how to obtain these regret bounds are provided at the end.) It is worth pointing out that the dependence on $S$, $A$, and $K$ stays the same and is sharp.\n\nTechnical details on how to show the $\\tilde{\\mathcal{O}}((D_{\\max}+1)^{3/2} H^{5/2} \\sqrt{SAK})$ regret.\n\n1) The cardinality of S_aug is bounded by $HSA^{D_{\\max}+1}$ now (Line 467 in Appendix B.1).\n\n2) The high probability event holds uniformly over S_aug. Therefore, the confidence band is narrowed by replacing $H$ with $D_{\\max} + 1$ in the square root.\n\n3) In Eqn. (B.7) and (B.10), we replace a factor of $H$ by $D_{\\max}+1$ as the delay is bounded by $D_{\\max}$.\n\nPutting 1), 2), and 3) together leads to the claimed regret bound.\n\n4) In the case of no delay, we do not need to estimate the distribution of delays. Therefore, the bonus function is simplified and there is no need to sum up in Eqn. (B.4). With these simplifications, we recover the regret bound in standard MDPs.\n\n>**Q4**: When the delay $d_h$ is 0. There is still a gap in the regret in Theorem 4.1?\n\n**A4**: Our regret in Theorem 4.1 is sharp in S, A, and K. As mentioned, we recover the minimax optimal dependence on S, A, and K in the standard MDP setting. Our analysis covers arbitrary delay in the worst case. When the length of delay is bounded, we can modify the regret bound as shown in the previous response A3.\n\n>**Q5**: When the missing rate is 0, the regret seems to be larger than the best regret?\n\n**A5**: In Proposition 5.1 (the last inequality above Line 558), when the observation rate $\\lambda_0$ is 1, i.e., no missing, we recover the same regret of optimistic planning in standard MDPs. Also, as discussed in Line 278 - 279, the dependence on the observation rate is approximately $1 / \\lambda_0^2$ (the square comes from consecutive observations for transition estimation).\n\nIn Theorem 5.2, the dependence of the missing rate appears in the non dominating term. When the missing rate is 0, i.e., $v = \\infty$, we can recover the regret bound in the standard MDPs with a slight modification on the proof similar response A3.\n\n>**Q6**: The executable policy class is defined based on the action sequence. However, based on the notation, the action is always known. Why is the action sequence $a_{t_h:h-1}$ important?\n\n**A6**: One has to keep track of past actions $a_{t_h:h-1}$ and choose actions based on them because they influence the current unknown state. It is necessary to augment state space with both past actions and the nearest observed state $s_{t_h}$, in order for the Markov property to hold and make the augmented MDP well defined. Missing any of $a_{t_h:h-1}$ would lead to incomplete information and ill-defined probability space.\n\n\n"}, {"review_id": "802UOFt9p9", "reviewer": "Reviewer_kTAd", "summary": "This paper aims to provide a theoretical analysis of reinforcement learning with delayed and missing state observations, and establish near-optimal regret bounds, for RL in both the delayed and missing observation settings. Despite impaired observability posing significant challenges to the policy class and planning, the results demonstrate that learning remains efficient, with the regret bound optimally depending on the state-action size of the original system.  The policy under impaired observability is evaluated.", "questions": "1. How can the theoretical analysis inspire further algorithm design to address impaired observations?\n2. What are the main challenges preventing you from conducting empirical studies for the proposed method?", "limitations": "1. The scalability for large action spaces is limited.\n2. The lack of empirical studies makes the applicability of the method uncertain.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The problem addressed is critical for applying RL to real-world scenarios.\n2. The theoretical analysis is comprehensive and well-executed.", "weaknesses": "1. The paper does not include preliminary experimental results, which may hinder the empirical understanding of the methods.\n2. Building connections between the theoretical analysis and existing empirical studies in the literature would be beneficial.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments!\n\n>**Q1**: The paper does not include preliminary experimental results, which may hinder the empirical understanding of the methods.\n\n**A1**: Thanks for the suggestion. In the RL theory literature, developing theory for tabular MDP is usually the first step, and most papers in this category did not need experiments due to the nature of tabular problems [1-3].\n\nIn contrast, we followed your suggestion and **conducted additional experiment on a toy model (see https://openreview.net/attachment?id=Pd2GMnkFUx&name=pdf for results)**. In particular, we consider constant delays and set the MDP with horizon $H = 6$. Detailed transitions and reward are summarized in Table 1 and Table 2  in the attached PDF. We vary the length of delay to be 1 and 2, and run our proposed policy learning Algorithm 2 for 10000 episodes. The regret is plotted in Figure 1. As can be seen, the regret increases as the length of delay increases. In Figure 2, we investigate the performance degradation caused by delayed observations. When the transition is almost deterministic, we observe that the gap is relatively small. However, when the transition is more random, the gap increases. These observations validate our main theory results such as Proposition B.2 and 4.2.\n\n[1] “Near-optimal reinforcement learning in polynomial time” by Michael Kearns and Satinder Singh.\n\n[2] “Minimax Regret Bounds for Reinforcement Learning” by Mohammad Gheshlaghi Azar, Ian Osband, Rémi Munos.\n\n[3] “Near-optimal regret bounds for reinforcement learning” by Thomas Jaksch, Ronald Ortner, and Peter Auer.\n\n>**Q2**: The scalability for large action spaces is limited.\n\n**A2**: Our main focus is the learning efficiency. The proposed algorithms actually work with any planning oracle and achieve polynomial sample complexity. Depending on the planning oracle to be chosen by a practical user, the time complexity might vary and would be exponential in only with the worst choice. In practice, one often solves the planning problem using policy gradient methods with function approximation, which proved quite efficient even in large-scale problems.\n"}, {"review_id": "BN56KAzuNt", "reviewer": "Reviewer_Mu3C", "summary": "The paper considers reinforcement learning with delayed and missing observations. It is shown that a MDP with delayed observations is equivalent to an augmented MDP with perfect observations. Based on the augmented MDP, an optimistic algorithm is proposed for delayed MDPs and it is shown to achieve a near-optimal regret order. For MDPs with missing observations, two optimistic algorithms are proposed with near-optimal regret order under some assumptions on the missing rate.", "questions": "- Can the authors fix some of the typos and missing steps?", "limitations": "Limitations are adequately addressed in the paper.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- For MDPs with delayed observations, under some independent assumption and an assumption requiring the delayed observations will still arrive in order, the paper constructs an equivalent augmented MDP with perfect observations. Based on the augmented MDP, an optimistic algorithm is proposed for the delayed MDP. Despite the increased cardinality of the augmented MDP, the proposed algorithm is shown to achieve a regret with sharp dependence on the state and action spaces. \n\n- The effect of observation delay on performance degradation is discussed with some performance gap bounds provided between the optimal policy with and without observation delays. \n\n- For MDPs with missing observations, one optimistic algorithm is proposed and its regret is shown to be sub-linear in the number of episodes.\n\n- When the missing rate is small, another algorithm based on the augmented MDP is proposed. This algorithm is shown to have near-optimal regret order if the number of episode is large enough.", "weaknesses": "- There are some possible typos in key equations which may highly affect the derivations and results.\n  - In the definition of the transition below line 164, the collections of actions for time $h$ and $h+1$ may have different sizes. Is that just some typo or some additional things need to be handled?\n  - In the equation above line 182, should the reward be $r_{t_h}$?\n  - In the bonus function in Algorithm 2, $a_h$ seems to be a typo.\n \n- There seems to be several missing steps in the proof of Proposition 5.1. The entire derivation of the proof should be conditioned on some high probability event for the inequalities to hold, but those steps are missing. Inequality (i) is claimed to be true from valid optimism, but optimism for Algorithm 3 is not provided. Inequality (ii) might also need some further discussion.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments!\n\n>**Q1**: In the definition of the transition below line 164, the collections of actions for time $h$ and $h+1$ may have different sizes. Is that just some typo or some additional things need to be handled?\n\n**A1**: Varying sizes of actions is a consequence of our general delay distribution, i.e., at time $h$, there is a possibility that there is no new state observation. We can only increase the action sequence in the augmented space. Yet our analysis tackles the varying sizes of actions. We bound the worst case cardinality of the augmented state space in Line 467 and the optimism holds for any augmented state.\n\n>**Q2**: In the equation above line 182, should the reward be $r_{t_h}$?\n\n**A2**: Thanks for pointing out the typo.\n\n>**Q3**: In the bonus function in algorithm 2, $a_h$ seems to be a typo.\n\n**A3**: Thanks for pointing out the typo.\n\n>**Q4**: There seems to be several missing steps in the proof of Proposition 5.1. The entire derivation of the proof should be conditioned on some high probability event for the inequalities to hold, but those steps are missing. Inequality (i) is claimed to be true from valid optimism, but optimism for Algorithm 3 is not provided. Inequality (ii) might also need some further discussion.\n\n**A4**: We are confident about the correctness and rigor of our proof. Thanks for the comment and we will add more clarifications. \n\nThe high probability event we are conditioned on is that the ground-truth transition (denoted by $\\theta^*$ notation) falls into the set $\\mathcal{B}_k$. This can be shown by a direct application of Hoeffding’s inequality. We will add this argument in the next version.\n\nInequality (i) of Proposition 5.1 follows from Line 4 of Algorithm 3. As the ground truth environment is contained in $\\mathcal{B}_k$, the value of the best executable policy for the ground truth environment is no larger than the largest value under the double maximization.\n\nInequality (ii) follows from a standard telescoping expansion of the value function over time by utilizing the fact that $Q_h(s, a) = r_h(s, a) +[P_h V_{h+1}](s, a)$ for any $h$. We apply this expansion to both $V_{\\theta^k}^{\\pi^k}$ and $V_{\\theta^*}^{\\pi^k}$."}, {"review_id": "o1LMp88rEU", "reviewer": "Reviewer_61zK", "summary": "This paper studies online learning in tabular MDPs with impaired observability, which means one of two models: states are observed in stochastic delay or some observations are missing (sampled independently). The authors present algorithms based on optimism and prove regret bounds that scale optimally with $S,A,K$ and polynomially with $H$.", "questions": "**Questions:**\n1. The definition of the augmented MDP is very hard to follow. Can that authors please explain in words what this MDP looks like?\n2. Can the authors please discuss the assumptions a little more? For example, is the assumption that feedback arrives in order necessary? what happens when there are large delays and why is the regret always bounded within $H$?\n3. Is the augmented MDP a factored MDP?\n4. Can you think of a scenario where the computational complexity is not exponential?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "**Summary:** I don't have a strong conviction about this paper. On the one hand the paper is well-written and the model is interesting and novel, but on the other hand the regret bounds are straightforward and there is no interesting algorithmic novelty in my opinion.\n\n**Strengths:**\n1. RL with impaired observability is an interesting model which obviously has a lot of real-world applications. The authors do a good job of introducing the model, the challenges and the motivation.\n2. The paper is generally well-written and easy to follow (except for a few technical parts, see questions). It conveys well the need for the impaired observability model and the idea behind the algorithmic approaches to solve it.\n3. The algorithms are simple and the regret bounds are close to optimal (although one can argue about what is close to optimal in this setting).", "weaknesses": "**Weaknesses:**\n1. I think that the novelty of this paper is limited to the definition of the new models. In terms of algorithmic contribution, the application of optimism here is straightforward and so is the regret analysis. In fact, unless I am missing something, the augmented MDP is a factored MDP and then the algorithms (and analysis) actually exist already, so there is no surprise that the regret is polynomial. If that is the case, then the authors should also discuss the factored MDP literature, e.g., \"Near-optimal Reinforcement Learning in Factored MDPs\" by Ian Osband and Benjamin Van Roy.\n2. The algorithms run in exponential time in $H$. I understand that this is probably inevitable, but it still makes the contributions of this paper very limited.\n3. The regret analysis is similar to previous works and does not investigate in-depth the dependence on the delays or the missing observations rate. The regret of algorithm 2 \"hides\" the dependence in the distribution of the delays in the extra $H$ factors. I think that the actual dependence is interesting in this setting because it can show which delays actually become a problem. While the dependence on the missing rate is shown in the regret of algorithm 3, the optimality is not discussed and instead there is an additional algorithm that replaces this optimality with another assumption (that to me looks like it makes the whole thing easy because very few observations are missing). Moreover, There is not enough discussion about the assumptions 2.1 and 2.2, and what happens if they are relaxed. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments!\n\n>**Q1**: The novelty of this paper is limited to the definition of the new models. It appears to be a factored MDP with known solutions.\n\n**A1**: We disagree respectfully. Our augmented MDP is not a factored MDP. Factored MDPs encode rewards and transitions exhibiting some conditional independence structure among factors. Although our augmented MDP has sparse transition probabilities, it does not have immediate conditional independence structures. Thus, there was no prior solution to the delayed MDP except for naive exponential-regret methods.\n\nMore importantly, we are first to provide concrete regret bounds scale with $\\sqrt{S A}$ by developing several novel techniques regarding the augmented MDP formulation and bonus function construction and analysis.\n\n1). To tackle the exponentially large state space in the augmented MDP, we construct a reformation tilde_MDP_aug with past reward and an extended horizon. This new reformulation provably attains the same expected reward as MDP_aug and serves as the basis of Algorithm 2.\n\n2). In Algorithm 2, we provide a novel construction on the bonus function to ensure optimism with high probability. The intriguing fact of the bonus function is that it is akin to the bonus of UCBVI applied to the original MDP. However, this is a consequence of our analysis exploiting the sparse structure in the transition kernel. A direct application of the UCBVI algorithm to tilde_MDP_aug will easily end up with annoying $N(s_{t_h}, a_{t_h:h-1})$ counting numbers, which leads to exponential regret. In addition, we also provide uncertainty quantification on the arbitrary delay distribution, which to our best knowledge is never done in prior work.\n\n>**Q2**: The algorithms run in exponential time.\n\n**A2**: There seems to be some misunderstanding. While our main focus is the learning efficiency, our proposed algorithms actually work with any planning oracle and achieve polynomial sample complexity. The technical contributions are discussed in response A1. Depending on the planning oracle to be chosen by a practical user, the time complexity might vary and would be exponential in $H$ only with the worst choice. In practice, one often solves the planning problem using policy gradient methods with function approximation, which proved quite efficient even in large-scale problems.\n\n>**Q3**: The regret analysis is similar to previous works and does not investigate in-depth the dependence on the delays or missing observations rate.\n\n**A3**: We do not assume any distribution on the length of delay. Hence, the regret bound holds for arbitrary delay in the worst case. The idea is that we consider finite-horizon MDPs, therefore, we can truncate the length of delay at $H$ (Line 221-225).\n\nWhen the delay is much better behaved, e.g., is bounded by some constant $D_{\\max}$ smaller than $H$, we can obtain better regret bounds. With the same algorithm, a very slight modification on our proof leads to a regret of $\\tilde{\\mathcal{O}}((D_{\\max}+1)^{3/2} H^{5/2} \\sqrt{SAK})$. As can be seen, when $D_{\\max}$ is small, the regret becomes small. Moreover, when $D_{\\max} = 0$, i.e., there is no delay, the regret recovers that in standard MDPs without delay.\n\nPlease also see the response A3 to **Reviewer yWj8** for technical details of how to obtain the modified regret bounds.\n\n>**Q4**: While the dependence on the missing rate is shown in the regret of algorithm 3, the optimality is not discussed and instead there is an additional algorithm that replaces this optimality with another assumption.\n\n**A4**: Proposition 5.1 confirms that obtaining polynomial regret with missing observations is possible. Yet the $S^2$ dependence may not be optimal. With an assumption on the missing rate, we indeed show a $\\sqrt{SA}$ regret, which matches the minimax optimal dependence on S, A in the standard MDP setting. We further discuss the assumption on the missing rate in Line 304 - 310, while leaving the study of missing rates larger than $1/A$ as future work.\n\nThe analysis to Theorem 5.2 is rather complicated, in contrast to the seemingly “easy” small missing rate. The major difficulty is to handle the summation over multi-step counting numbers (from Line 593 to the end of Appendix C). \n\n>**Q5**: Moreover, there is not enough discussion about the assumptions 2.1 and 2.2, and what happens if they are relaxed.\n\n**A5**: Assumption 2.1 and 2.2 are fairly general themselves and encode arbitrary delay and missing distributions (see a discussion in Line 123-127). Our theory holds even in the worst scenario.\n\nTo further relax Assumption 2.1 and 2.2, such as allowing interarrival time $\\Delta_h$ to be negative, i.e., $s_{h}$ can be observed before $s_{h-1}$, and missing rate dependent on the underlying state, goes beyond the scope of the current paper. \n\n>**Q6**: The definition of the augmented MDP is very hard to follow.\n\n**A6**: Roughly speaking, the augmented MDP is to form an enlarged state space with the nearest observed state and all the history actions thereafter (see definition of $\\tau_h$ in Line 154). The reward and transition probabilities are slightly complicated, but built upon the original MDP. The reward function is the expected reward (Line 157 - 158) over the belief of the unseen current state, given all the observed information. The transition probabilities are sparse, as past actions cannot be altered (Line 164 - 165).\n\n>**Q7**: A scenario where the computational complexity is not exponential?\n\n**A7**: While investigating practical planning algorithms for specific problem is beyond the scope of our paper, we believe that our augmented MDP formation is compatible with *any* planning oracle for accelerated solution of RL.\n\nAs a particular example, when the underlying transition is nearly deterministic, Thomas J Walsh, Ali Nouri, Lihong Li, and Michael L Littman. “Planning and learning in environments with delayed feedback” show a polynomial planning complexity.\n"}]

Author rebuttal:
We would like to thank all the reviewers for a thoughtful review and valuable comments, which help to improve the quality of the paper. We have provided our response to your individual questions and concerns.

In addition to clarify our contributions and technical novelties, we conduct numerical experiments as suggested by Reviewer kTAd. The results are summarized in the attached PDF file.

Meta-review: The paper considers a modified MDP setting when either the observations are delayed or some of the observations are missing altogether. To solve this problem, it constructs an augmented MDP and proposes optimistic methods to solve them. The methods have regret guarantees, which in some cases is sharp. The paper also provides a result showing the gap between the optimal policy with no-delay MDP and with-delay MDP.

The reviewers are positive about this paper. We have two Borderline Accept, one Weak Accept, and One Accept. They believe that the problem is critical for applying RL to real-world scenarios, the theoretical analysis is well-executed, and the guarantees are sharp.

The reviewers mentioned a few shortcomings of the paper. Some of them are:

- The lack of experimental results (Reviewer kTAd).
The authors provided some preliminary empirical results during the rebuttal, so this is partially addressed.

- Difficulty of understanding how the augmented MDP is constructed (Reviewer 61zK).
I agree with this, and I hope the authors can provide some intuition about the construct. If the detail is not important for the main message of the paper, perhaps it can be postponed to an appendix.

- There has been concerns about the novelty of this work, especially interestingness of the algorithms, and the regret analysis following standard techniques or not (Reviewers yWj8 and 61zK).
The problem setup appears to be novel and is not reduced to any known setup. Naive approach does not get to the same regret. As these criticisms are more on the subjective side, I am not giving a significant weight to them.

- Missing steps in the the proof of Proposition 5.1 (Reviewer Mu3C).
I read this proof. It follows a pretty standard line of argument, though I suggest expanding it a bit to make it more accessible.

Overall, I believe **this is a technically good paper that should be accepted** at NeurIPS.
Decision: Accept (poster)