We study the model‐based undiscounted reinforcement learning for partially observable Markov decision processes (POMDPs). The oracle we consider is the optimal policy of the POMDP with a known environment in terms of the average reward over an infinite horizon. We propose a learning algorithm for this problem, building on spectral method‐of‐moments estimations for hidden Markov models, the belief error control in POMDPs and upper confidence bound methods for online learning. We establish a regret bound of for the proposed learning algorithm where T is the learning horizon. This is, to the best of our knowledge, the first algorithm achieving sublinear regret with respect to our oracle for learning general POMDPs.
AgrawalS.JiaR. (2017). Optimistic posterior sampling for reinforcement learning: worst‐case regret bounds. Advances in Neural Information Processing Systems, 30, 1184–1194.
2.
AnandkumarA.GeR.HsuD.KakadeS. M.TelgarskyM. (2014). Tensor decompositions for learning latent variable models. Journal of Machine Learning Research, 15, 2773–2832.
3.
AnandkumarA.HsuD.KakadeS. M. (2012). A method of moments for mixture models and hidden Markov models. In Mannor, Shie, Srebro, Nathan & Williamson, Robert C. (Eds.), Conference on learning theory (Vol. 23, pp. 33.1–33.34), PMLR.
4.
AuerP.Cesa‐BianchiN.FischerP. (2002a). Finite‐time analysis of the multiarmed bandit problem. Machine Learning, 47(2), 235–256.
5.
AuerP.Cesa‐BianchiN.FreundY.SchapireR. E. (2002b). The nonstochastic multiarmed bandit problem. SIAM Journal on Computing, 32(1), 48–77.
6.
AuerP.GajaneP.OrtnerR. (2019). Adaptively tracking the best bandit arm with an unknown number of distribution changes. In Beygelzimer, Alina & Hsu, Daniel (Eds.), Conference on learning theory (Vol. 99, pp. 138–158), PMLR.
7.
AuerP.OrtnerR. (2006). Logarithmic online regret bounds for undiscounted reinforcement learning. In SchölkopfB.PlattJ.HoffmanT. (Eds.), Advances in Neural Information Processing Systems, (Vol. 19, pp. 49–56), MIT Press.
8.
AzarM. G.OsbandI.MunosR. (2017). Minimax regret bounds for reinforcement learning. In Precup, Doina & Teh, Yee Whye (Eds.), International conference on machine learning (Vol. 70, pp. 263–272), PMLR.
9.
AzizzadenesheliK.LazaricA.AnandkumarA. (2016). Reinforcement learning of POMDPs using spectral methods. In Feldman, Vitaly, Rakhlin, Alexander & Shamir, Ohad (Eds.), Conference on learning theory (Vol. 49, pp. 193–256), PMLR.
10.
BalakrishnanS.WainwrightM.YuB. (2017). Statistical guarantees for the EM algorithm: From population to sample‐based analysis. The Annals of Statistics, 45(1), 77–120.
11.
BesbesO.GurY.ZeeviA. (2014). Stochastic multi‐armed‐bandit problem with non‐stationary rewards. Advances in Neural Information Processing Systems, 27, 199–207.
12.
BubeckS.Cesa‐BianchiN. (2012). Regret analysis of stochastic and nonstochastic multi‐armed bandit problems. Machine Learning, 5(1), 1–122.
13.
CaoX.GuoX. (2007). Partially observable Markov decision processes with reward information: Basic ideas and models. IEEE Transactions on Automatic Control, 52(4), 677–681.
14.
ChenB.ChaoX.AhnH. (2019). Coordinating pricing and inventory replenishment with nonparametric demand learning. Operations Research, 67(4), 1035–1052.
15.
ChenN.WangC.WangL. (2021). Learning and optimization with seasonal patterns. ArXiv preprint arXiv:2005.08088.
16.
ChenW.ShiC.DuenyasI. (2020). Optimal learning algorithms for stochastic inventory systems with random capacities. Production and Operations Management, 29(7), 1624–1649.
17.
CheungW.Simchi‐LeviD.ZhuR. (2019). Non‐stationary reinforcement learning: The blessing of (more) optimism. Available at SSRN 3397818.
18.
CheungW.Simchi‐LeviD.ZhuR. (2022). Hedging the drift: Learning to optimize under nonstationarity. Management Science, 68(3), 1696–1713.
19.
De CastroY.GassiatE.Le CorffS. (2017). Consistent estimation of the filtering and marginal smoothing distributions in nonparametric hidden Markov models. IEEE Transactions on Information Theory, 63(8), 4758–4777.
20.
FiezT.SekarS.RatliffL. (2018). Multi‐armed bandits for correlated Markovian environments with smoothed reward feedback. ArXiv preprint arXiv:1803.04008.
21.
GarivierA.MoulinesE. (2011). On upper‐confidence bound policies for switching bandit problems. In Kivinen, Jyrki, Szepesvári, Csaba, Ukkonen, Esko & Zeugmann, Thomas (Eds.), International conference on algorithmic learning theory (pp. 174–188), Springer Berlin Heidelberg.
22.
GuhaS.MunagalaK.ShiP. (2010). Approximation algorithms for restless bandit problems. Journal of the ACM (JACM), 58(1), 1–50.
23.
GuoZ.DoroudiS.BrunskillE. (2016). A PAC RL algorithm for episodic POMDPs. In Gretton, Arthur & Robert, Christian C. (Eds.), International conference on artificial intelligence and statistics (pp. 510–518), PMLR.
24.
HausknechtM.StoneP. (2015). Deep recurrent q‐learning for partially observable MDPS. In Association for the advancement of artificial intelligence fall symposium series (pp. 29–37).
25.
HindererK. (2005). Lipschitz continuity of value functions in Markovian decision processes. Mathematical Methods of Operations Research, 62(1), 3–22.
26.
HsuS.ChuangD.ArapostathisA. (2006). On the existence of stationary optimal policies for partially observed MDPS under the long‐run average cost criterion. Systems & Control Letters, 55(2), 165–173.
27.
IglM.ZintgrafL.LeT.WoodF.WhitesonS. (2018). Deep variational reinforcement learning for POMDPs. In Dy, Jennifer & Krause, Andreas (Eds.), International conference on machine learning (pp. 2117–2126), PMLR.
28.
JakschT.OrtnerR.AuerP. (2010). Near‐optimal regret bounds for reinforcement learning. The Journal of Machine Learning Research, 11, 1563–1600.
29.
JinC.Allen‐ZhuZ.BubeckS.JordanM. (2018). Is Q‐learning provably efficient?Advances in Neural Information Processing Systems, 31, 4868–4878.
30.
JinC.KakadeS.KrishnamurthyA., & Liu (2020). Sample‐efficient reinforcement learning of undercomplete POMDPs. Advances in Neural Information Processing Systems, 33, 18530–18539.
31.
KeskinN.ZeeviA. (2017). Chasing demand: Learning and earning in a changing environment. Mathematics of Operations Research, 42(2), 277–307.
32.
KrishnamurthyV. (2016). Partially observed Markov decision processes. Cambridge University Press.
33.
KwonJ.EfroniY.CaramanisC.MannorS. (2021). Rl for latent MDPS: Regret guarantees and a lower bound. Advances in Neural Information Processing Systems, 34, 24523–24534.
34.
LakshmananK.OrtnerR.RyabkoD. (2015). Improved regret bounds for undiscounted continuous reinforcement learning. In Bach, Francis & Blei, David (Eds.), International conference on machine learning (pp. 524–532), PMLR.
35.
LattimoreT.SzepesváriC. (2020). Bandit algorithms. Cambridge University Press.
36.
LehéricyL. (2019). Consistent order estimation for nonparametric hidden Markov models. Bernoulli, 25(1), 464–498.
37.
NambiarM.Simchi‐LeviD.WangH. (2021). Dynamic inventory allocation with demand learning for seasonal goods. Production and Operations Management, 30(3), 750–765.
38.
OrmoneitD.GlynnP. (2002). Kernel‐based reinforcement learning in average‐cost problems. IEEE Transactions on Automatic Control, 47(10), 1624–1636.
39.
OrtnerR.RyabkoD. (2012). Online regret bounds for undiscounted continuous reinforcement learning. In PereiraF.BurgesC.J.BottouL.WeinbergerK.Q. (Eds.), Advances in Neural Information Processing Systems, (Vol. 25, 1772–1780), Curran Associates, Inc.
RossS. (1968). Arbitrary state Markovian decision processes. The Annals of Mathematical Statistics, 39(6), 2118–2122.
43.
RossS.PineauJ.Chaib‐draaB.KreitmannP. (2011). A Bayesian approach for learning and planning in partially observable Markov decision processes. The Journal of Machine Learning Research, 12, 1729–1770.
SaldiN.YükselS.LinderT. (2017). On the asymptotic optimality of finite approximations to Markov decision processes with Borel spaces. Mathematics of Operations Research, 42(4), 945–978.
46.
SharmaH.Jafarnia‐JahromiM.JainR. (2020). Approximate relative value learning for average‐reward continuous state MDPS. In Adams, Ryan P. & Gogate, Vibhav (Eds.), Conference on uncertainty in artificial intelligence (pp. 956–964), PMLR.
47.
SlivkinsA.UpfalE. (2008). Adapting to a changing environment: The Brownian restless bandits. In Rocco, Servedio & Tong, Zhang (Eds.), Conference on learning theory (pp. 343–354), PMLR.
StephensM. (2000). Dealing with label switching in mixture models. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 62(4), 795–809.
50.
SuttonR.BartoA. (2018). Reinforcement learning: An introduction. MIT Press.
51.
YangF.BalakrishnanS.WainwrightM. (2017). Statistical and computational guarantees for the Baum‐Welch algorithm. The Journal of Machine Learning Research, 18(1), 4528–4580.
52.
YuH.BertsekasD. (2004). Discretized approximations for POMDP with average cost. In Christopher Meek (Ed.), Conference on uncertainty in artificial intelligence (pp. 619–627), AUAI Press.
53.
YuH.BertsekasD. (2008). On near optimality of the set of finite‐state controllers for average cost POMDP. Mathematics of Operations Research, 33(1), 1–11.
54.
ZhangH.ChaoX.ShiC. (2018). Perishable inventory systems: Convexity results for base‐stock policies and learning algorithms under censored demand. Operations Research, 66(5), 1276–1286.
55.
ZhangH.ChaoX.ShiC. (2020). Closing the gap: A learning algorithm for lost‐sales inventory systems with lead times. Management Science, 66(5), 1962–1980.
56.
ZhangZ.JiX. (2019). Regret minimization for reinforcement learning by evaluating the optimal bias function. Advances in Neural Information Processing Systems, 32, 2827–2836.
57.
ZhaoJ.XieX.XuX.SunS. (2017). Multi‐view learning overview: Recent progress and new challenges. Information Fusion, 38, 43–54.
58.
ZhouX.XiongY.ChenN.GaoX. (2021). Regime switching bandits. In RanzatoM.BeygelzimerA.DauphinY.LiangP.S.Wortman VaughanJ. (Eds.), Advances in Neural Information Processing Systems, 34, (pp. 4542–4554).
59.
ZhuF.ZhengZ. (2020). When demands evolve larger and noisier: Learning and earning in a growing environment. In III, Hal Daumé & Singh, Aarti (Eds.), International conference on machine learning (Vol. 119, pp. 11629–11638), PMLR.
