Markov Decision Processes: Estimation and Approximate Solutions  Page description

Help  Print 
Back »
 

Details of project

  
Identifier
125698
Type KH
Principal investigator Csáji, Balázs Csanád
Title in Hungarian Markov döntési folyamatok becslése és közelítő megoldása
Title in English Markov Decision Processes: Estimation and Approximate Solutions
Keywords in Hungarian Markov láncok, szekvenciális optimalizálás, becsléselmélet, véletlen algoritmusok
Keywords in English Markov chains, sequential optimization, estimation theory, randomized algorithms
Discipline
Operational Research (Council of Physical Sciences)40 %
Ortelius classification: Operations research
Economics (Council of Humanities and Social Sciences)40 %
Ortelius classification: Biometrics
Computing Science (Council of Physical Sciences)20 %
Panel Mathematics and Computing Science
Department or equivalent HUN-REN Institute for Computer Science and Control
Participants Bergmann, Júlia
Kis, Krisztián Balázs
Starting date 2017-09-01
Closing date 2019-08-31
Funding (in million HUF) 15.048
FTE (full time equivalent) 2.64
state closed project
Summary in Hungarian
A kutatás összefoglalója, célkitűzései szakemberek számára
Itt írja le a kutatás fő célkitűzéseit a témában jártas szakember számára.
A hosszútávú (a projekten túlmutató) cél Markov döntési folyamatok egyidejű becslésének és irányításának egyensúlyba hozása, a felfedezés-vs-kihasználás dilemmájának minél általánosabb megoldása. A probléma alapvetően abban áll, hogy ha úgy választjuk meg a rendszer bemeneteit (a döntéseinket), hogy az minél több információval szolgáljon a folyamatról magáról, akkor ez ellentétes irányba fog hatni azzal a törekvésünkkel, hogy olyan döntéseket szeretnénk hozni, amelyek minimalizálják a várható (átlagos vagy diszkontált) kumulatív költségeket. A probléma megoldása szempontjából kulcs fontosságú, hogy ne csak pontbecslésekkel rendelkezzünk a folyamatról (beleértve a költségeket), hanem konfidencia tartományaink is legyenek a becsléseinkhez. A másik fontos terület a dilemma megoldásához, hogy minél jobban megértsük a véletlenítés hatásait a megoldási módszerekben, ugyanis a jenlegi módszerek egy jó része véletlenítésen alapul. A projekt célja ezen területeken való előrelépés. Konkrétan: (irányított) Markov reprezentációval rendelkező dinamikus rendszerek pontbecslései köré építhető konfidencia tartományok vizsgálata; valamint a véletlenített módszerek tanulmányozása mind a szekvenciális döntési problémák mind a fent említett konfidencia tartomány becslések szempontjából.

Mi a kutatás alapkérdése?
Ebben a részben írja le röviden, hogy mi a kutatás segítségével megválaszolni kívánt probléma, mi a kutatás kiinduló hipotézise, milyen kérdéseket válaszolnak meg a kísérletek.
Markov döntési problémákat (MDP) széles körben alkalmaznak a gyakorlatban, a statisztikus gépi tanulástól, az irányításelméleten és jelfeldolgozáson át a közgazdaságtanig. Egy alapvető kérdés, hogy hogyan becsüljünk (irányított) Markov modelleket tapasztalati adatokból, esetleg a rendszer bemeneteinek "ügyes" megválasztásával. Egy másik klasszikus probléma osztály, hogy hogyan számoljunk rekurzívan irányítási politikákat MDP-khez, amelyek egy adott azonnali költségfüggvény kumulatív (tipikusan átlagos vagy diszkontált) várható értéket minimalizálják. A két problémát a gyakorlatban sokszor egyszerre kell megoldani, azonban, a rendszer hatékony becslése (információ szerzés) és a költségek minimalizálása (az információ kihasználása) egymás ellen ható szempontok. A folyamat becslésének és hatékony irányításának egyensúlyba hozása egy fundamentális probléma, amelynek általános megoldása túlmutat a projekt keretein, de a projekt megcélzott kérdései (konfidencia halmaz konstrukciók valamint véletlenítési eljárások vizsgálata) ebből merítik a motivációjukat.

Mi a kutatás jelentősége?
Röviden írja le, milyen új perspektívát nyitnak az alapkutatásban az elért eredmények, milyen társadalmi hasznosíthatóságnak teremtik meg a tudományos alapját. Mutassa be, hogy a megpályázott kutatási területen lévő hazai és a nemzetközi versenytársaihoz képest melyek az egyediségei és erősségei a pályázatának!
A Markov döntési folyamatok nagyon általános modelljei bizonytalansággal terhelt szekvenciális döntési problémáknak. Előrelépés az ilyen problémák jobb megértésében és hatékonyabb módszerek kutatása hatással van az ezen modelleket és módszereket alkalmazó számos tudományterület fejlődésére (beleértve a gépi tanulást és az irányításelméletet). A vezető kutató számos éve foglalkozik Markov döntési folyamatokkal és több fontos eredménye van nem-aszimptotikus félparametrikus konfidencia tartományok építésével kapcsolatban, dinamikus rendszermodellek esetén is.

A kutatás összefoglalója, célkitűzései laikusok számára
Ebben a fejezetben írja le a kutatás fő célkitűzéseit alapműveltséggel rendelkező laikusok számára. Ez az összefoglaló a döntéshozók, a média, illetve az érdeklődők tájékoztatása szempontjából különösen fontos az NKFI Hivatal számára.
Szekvenciális döntéshozás bizonytalansággal terhelt dinamikus (változó) rendszerekben, valamilyen költség optimalizálása céljából egy rendkívül általános feladat, amely nagyon sokszor előkerül a gyakorlatban. Egy probléma, hogy gyakran nem rendelkezünk kellő tudással arról a környezetről, amelyben működni akarunk, ezért információkat kell gyűjtenünk a rendszerről. Mivel a rendszer működését befolyásolják a döntéseink, ezért "felfedező" döntésekre is szükség van a hatékony információgyűjtésre. A felfedező döntések azonban lényegüknél fogva kockázatosak. Az ismeretek bővítésének és kihasználásának egyensúlyba hozása egy kulcskérdés ilyen esetekben. A vázolt probléma általános megoldása túlmutat a projekt keretein, de a megcélzott kutatások ehhez visznek közelebb. Például konfidencia tartományok építése segít mérni a kockázatot amit egy döntésünkkel vállalunk, valamint bizonytalan rendszerekben is működni tudó rekurzív algoritmusok elemzése megalapozza a döntési stratégiák adaptív beállítását.
Summary
Summary of the research and its aims for experts
Describe the major aims of the research for experts.
The long-term goal of the studies (though its general solution is outside the scope of the current project) is to understand and solve the exploration-exploitation dilemma arising in Markov decision processes. The dilemma comes from the fact that if we choose our decisions in such a way that maximizes our information gain about the system (exploration), then it usually counteracts our other goal to make decisions whose cumulative (discounted or average) cost is minimal based on our current knowledge (exploitation). One of the key issues to solve this dilemma is to have efficient confidence region estimators available for Markov processes, as they can help assessing the risk making exploratory moves. Another important concept to study is the efficient use of randomization in such problems, as many available methods applies this idea. The actual goal of the project is to make progress in the direction of solving the fundamental dilemma in the two fields mentioned above. Particularly, an aim of the project is to investigate methods that can construct confidence regions (with finite sample guarantees) for semi-parametric models of controlled Markov chains and to study the use of randomization both on sequential decision problems and on the targeted confidence region constructions.

What is the major research question?
Describe here briefly the problem to be solved by the research, the starting hypothesis, and the questions addressed by the experiments.
Markov decision processes (MDPs) are general models of sequential decision making in uncertain, dynamical environments. They have a wide range of applications from computer science and control engineering to economics and finance. One of the fundamental questions is how to estimate (controlled) Markov models from experimental data, potentially by also making exploratory decisions. Another classical question is how to design good control policies which minimize some expected (discounted or average) cumulative costs. In many applications these two problems should be solved simultaneously, though they are against each other. Finding an equilibrium between exploratory (which help estimating the system) and exploitive (which use the gathered information) decisions is a fundamental problem whose general solution is the long-term goal, but it is out-of-scope for this project. On the other hand, this motivates the targers of the project, namely to investigate confidence region constructions and randomized decision mechanisms.

What is the significance of the research?
Describe the new perspectives opened by the results achieved, including the scientific basics of potential societal applications. Please describe the unique strengths of your proposal in comparison to your domestic and international competitors in the given field.
Markov decisions processes (MDPs) are very general models of sequential decision making in uncertain environments. Making progress in understanding fundamental questions related to MDPs and designing efficient methods could have a significant effect on other fields which apply Markovian models (such fields include, e.g., machine learning and control engineering). The principal investigator has several years of experience in MDPs and designing semi-parametric confidence region constructions (with non-asymptotic guarantees) for dynamical systems.

Summary and aims of the research for the public
Describe here the major aims of the research for an audience with average background information. This summary is especially important for NRDI Office in order to inform decision-makers, media, and others.
Sequential decision making in uncertain and changing (dynamic) environments, in order to minimize costs is a very general problem which arises in a wide range of applications. A problem in practice is that we usually do not have enough information about the environment that we are working in. Since, we may influence the system with our decisions, we can make "exploratory" decisions to efficiently gather information. However, such decisions are risky by nature, they have a highly uncertain cost. Finding a balance between exploring the environment and exploiting the gathered information is a fundamental problem whose general solution is outside the scope of the project, but it deeply motivates the targeted research, which makes progress in this direction. Namely, studying and designing confidence region constructions is crucial for assessing the risk of certain decisions, and investigating randomized methods helps finding the aforementioned balance, moreover, they also help creating approximate solutions to large-scale decision problems.




 

Final report

  
Results in Hungarian
A Markov döntési problémák (MDP-k) a bizonytalan és dinamikusan változó környezetekben való szekvenciális döntéshozás alapvető, széles körben használt modelljei. A gyakorlatban előforduló problémák többségénél nem ismerjük a környezet dinamikáját, azt a rendszerrel való interakciókon keresztül kell megtanulni, amit összhangba kell hoznunk az eddigi ismereteink alapján való eredményes működéssel. A projekt célja néhány olyan terület kutatása volt, amelyek alapvető fontosságúak az MDP-k hatékony megoldása szempontjából. A két kitűzött kutatási irány a (1) nem-aszimptotikus garanciákkal rendelkező konfidencia tartomány konstrukciók és a (2) sztochasztikus approximációs algoritmusok voltak. Az (1) iránnyal kapcsolatban új eloszlás-független módszereket dolgoztunk ki, valamint általánosítottuk a már korábban kidolgozott módszereket, mint amilyen az SPS algoritmus. Megvizsgáltuk, hogy hogyan befolyásolhatók az SPS konfidencia tartományok várható méretei a bemenetek alkalmas megválasztásával, valamint kiterjesztettük a módszert regularizált célfüggvények esetére. Egy alacsonyabb számítási igényű korrelációs algoritmust is bevezettünk, valamint kernel alapú klasszifikációs és regressziós módszerekhez is javasoltunk eloszlás-független konfidencia tartomány konstrukciókat. A (2) iránnyal kapcsolatban vizsgáltuk, hogy hogyan gyorsíthatók klasszikus módszerek, pl., az LMS algoritmus, valamint Markov dinamikájú rendszerek esetén elemeztük a paraméter-függő Poisson egyenletek megoldásait.
Results in English
Markov decision processes (MDPs) are widespread models of sequential decision making in uncertain and dynamical environments. In practice, the dynamics of the systems are often unknown and should be estimated via interactions with the system. In these cases, we should carefully balance between exploring the system and exploiting the gathered information. The project aimed at providing foundational studies which help efficiently solving MDPs. The two main research directions were: (1) constructions of non-asymptotic confidence regions (which are vital for the aforementioned exploration-exploitation dilemma); and (2) investigating stochastic approximation methods (which is a general theory behind most recursive algorithms for MDPs). Regarding (1), new methods as well as extensions of earlier ones, such as SPS (Sign-Perturbed Sums), were studied. The effects of input design on the expected sizes of SPS confidence sets was analyzed and SPS was also extended to handle regularized estimates. A computationally lighter correlation-based alternative was also suggested, and distribution-free, kernel-based, resampling-style confidence region constructions were proposed, too, for both regression and classification problems. Regarding (2), the effects of momentum acceleration on the LMS (least mean square) adaptive filter was studied as well as the solutions of parameter-dependent Poisson equations were analyzed for Markovian systems (e.g., existence, uniqueness and Lipschitz continuity).
Full text https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=125698
Decision
Yes





 

List of publications

  
Csáji, B. Cs.; Kis, K.: Distribution-Free Uncertainty Quantification for Kernel Methods by Gradient Perturbations, Machine Learning, Volume 108, pp 1677–1699, 2019
Csáji, B. Cs.; Kemény, Zs.; Pedone, G.; Kuti, A.; Váncza, J.: Wireless Multi-Sensor Networks for Smart Cities: A Prototype System with Statistical Data Analysis, IEEE Sensors Journal, Vol. 17, Issue 23, Dec 1, 2017, pp. 7667–7676, 2017
Csáji, B. Cs.; Kemény, Zs.; Pedone, G.; Kuti, A.; Váncza, J.: Wireless Multi-Sensor Networks for Smart Cities: A Prototype System with Statistical Data Analysis, IEEE Sensors Journal, Volume 17, Issue 23, Dec 1, 2017, pp. 7667–7676, 2017
Carè, A.; Csáji, B. Cs.; Campi, M. C.; Erik, W: Finite-Sample System Identification: An Overview and a New Correlation Method, IEEE Control Systems Letters, Volume: 2, Issue: 1, pp. 61 - 66, 2018
Carè, A.; Csáji, B. Cs.; Campi, M. C.; Erik, W: Finite-Sample System Identification: An Overview and a New Correlation Method, 56th IEEE Conference on Decision and Control (CDC 2017), Melbourne, Australia, December 12-15, 2017, pp. 4612-4617, 2017
Kolumbán, S.; Csáji, B. Cs.: Towards D-Optimal Input Design for Finite-Sample System Identification, 18th IFAC Symposium on System Identification (SYSID 2018), Stockholm, Sweden, July 9-11, 2018, pp. 215-220, 2018
Csáji, B. Cs.: Regularization in Finite-Sample System Identification, The 20th European Conference on Mathematics for Industry (ECMI), 18-22 June 2018, Budapest, Hungary, Book of Abstracts, pp., 247, 2018
Carè, A.; Csáji, B. Cs.; Campi, M. C.; Erik, W: Old and New Challenges in Finite-Sample Identification, The 20th European Conference on Mathematics for Industry (ECMI), 18-22 June 2018, Budapest, Hungary, Book of Abstracts, pp., 248, 2018
Csáji, B. Cs.: Szimmetria és konfidencia, Alkalmazott Matematikai Lapok, Volume 36, Issue 2, 2019
Carè; A.; Csáji, B. Cs.; Gerencsér, B.; Gerencsér, L; Rásonyi, M.: Parameter-Dependent Poisson Equations: Tools for Stochastic Approximation in a Markovian Framework, 58th IEEE Conference on Decision and Control (CDC), Nice, France, 2019
Gerencsér, L.; Csáji, B. Cs.; Sabanis, S.: Asymptotic Analysis of the LMS Algorithm with Momentum, 57th IEEE Conference on Decision and Control (CDC 2018), Miami Beach, Florida, December 17-19, 2018, 2018
Csáji, B. Cs.: Szimmetria és konfidencia, Alkalmazott Matematikai Lapok, 2019
Gerencsér, L.; Csáji, B. Cs.; Sabanis, S.: Asymptotic Analysis of the LMS Algorithm with Momentum, 57th IEEE Conference on Decision and Control (CDC 2018), Miami Beach, Florida, December 17-19, pp. 3062- 3067, 2018
Csáji, B. Cs., Tamás, A.: Semi-Parametric Uncertainty Bounds for Binary Classification, 58th IEEE Conference on Decision and Control (CDC), Nice, France, 2019
Egri, P.; Csáji, B. Cs.; Kis, K. B.; Monostori, L.; Váncza, J.; Ochs, J.; Jung, S.; König, N.; Schmitt, R.: Bio-Inspired Control of Automated Stem Cell Production, 13th CIRP Conference on Intelligent Computation in Manufacturing Engineering (ICME), Ischia, Naples, Italy, 2019
Csáji, B. Cs.: Non-Asymptotic Confidence Regions for Regularized Linear Regression, Progress in Industrial Mathematics at ECMI 2018, Springer, 2019
Csáji, B. Cs., Tamás, A., Kis, K. B.: Non-Asymptotic Uncertainty Bounds for Kernel Estimates, 30th European Conference on Operations Research, Dublin, Ireland, 2019
Csáji, B. Cs.: Statisztikus tanuláselmélet: klasszifikáció és regresszió sztochasztikus garanciákkal, XXXIII. Magyar Operációkutatási Konferencia, Szeged, 2019




 

Events of the project

  
2019-10-15 16:12:44
Résztvevők változása
2018-11-07 09:43:56
Résztvevők változása



Back »