[{"scopus_import":"1","acknowledgement":"This work was supported in part by the ERC-2020-AdG 101020093, ERC CoG 863818 (FoRM-SMArt) and the European Union’s Horizon 2020 research and innovation programme\r\nunder the Marie Skłodowska-Curie Grant Agreement No. 665385.","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","issue":"7","oa":1,"intvolume":"        36","volume":36,"related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"14539"}]},"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2112.09495"}],"date_created":"2023-02-05T17:29:50Z","external_id":{"arxiv":["2112.09495"]},"project":[{"name":"Vigilant Algorithmic Monitoring of Software","grant_number":"101020093","_id":"62781420-2b32-11ec-9570-8d9b63373d4d","call_identifier":"H2020"},{"name":"Formal Methods for Stochastic Models: Algorithms and Applications","grant_number":"863818","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","call_identifier":"H2020"},{"_id":"2564DBCA-B435-11E9-9278-68D0E5697425","grant_number":"665385","call_identifier":"H2020","name":"International IST Doctoral Program"}],"_id":"12511","page":"7326-7336","publication":"Proceedings of the AAAI Conference on Artificial Intelligence","ec_funded":1,"date_published":"2022-06-28T00:00:00Z","article_processing_charge":"No","keyword":["General Medicine"],"month":"06","date_updated":"2025-07-14T09:09:58Z","title":"Stability verification in stochastic control systems via neural network supermartingales","article_type":"original","type":"journal_article","citation":{"ista":"Lechner M, Zikelic D, Chatterjee K, Henzinger TA. 2022. Stability verification in stochastic control systems via neural network supermartingales. Proceedings of the AAAI Conference on Artificial Intelligence. 36(7), 7326–7336.","mla":"Lechner, Mathias, et al. “Stability Verification in Stochastic Control Systems via Neural Network Supermartingales.” <i>Proceedings of the AAAI Conference on Artificial Intelligence</i>, vol. 36, no. 7, Association for the Advancement of Artificial Intelligence, 2022, pp. 7326–36, doi:<a href=\"https://doi.org/10.1609/aaai.v36i7.20695\">10.1609/aaai.v36i7.20695</a>.","ama":"Lechner M, Zikelic D, Chatterjee K, Henzinger TA. Stability verification in stochastic control systems via neural network supermartingales. <i>Proceedings of the AAAI Conference on Artificial Intelligence</i>. 2022;36(7):7326-7336. doi:<a href=\"https://doi.org/10.1609/aaai.v36i7.20695\">10.1609/aaai.v36i7.20695</a>","chicago":"Lechner, Mathias, Dorde Zikelic, Krishnendu Chatterjee, and Thomas A Henzinger. “Stability Verification in Stochastic Control Systems via Neural Network Supermartingales.” <i>Proceedings of the AAAI Conference on Artificial Intelligence</i>. Association for the Advancement of Artificial Intelligence, 2022. <a href=\"https://doi.org/10.1609/aaai.v36i7.20695\">https://doi.org/10.1609/aaai.v36i7.20695</a>.","ieee":"M. Lechner, D. Zikelic, K. Chatterjee, and T. A. Henzinger, “Stability verification in stochastic control systems via neural network supermartingales,” <i>Proceedings of the AAAI Conference on Artificial Intelligence</i>, vol. 36, no. 7. Association for the Advancement of Artificial Intelligence, pp. 7326–7336, 2022.","apa":"Lechner, M., Zikelic, D., Chatterjee, K., &#38; Henzinger, T. A. (2022). Stability verification in stochastic control systems via neural network supermartingales. <i>Proceedings of the AAAI Conference on Artificial Intelligence</i>. Association for the Advancement of Artificial Intelligence. <a href=\"https://doi.org/10.1609/aaai.v36i7.20695\">https://doi.org/10.1609/aaai.v36i7.20695</a>","short":"M. Lechner, D. Zikelic, K. Chatterjee, T.A. Henzinger, Proceedings of the AAAI Conference on Artificial Intelligence 36 (2022) 7326–7336."},"quality_controlled":"1","language":[{"iso":"eng"}],"status":"public","abstract":[{"lang":"eng","text":"We consider the problem of formally verifying almost-sure (a.s.) asymptotic stability in discrete-time nonlinear stochastic control systems. While verifying stability in deterministic control systems is extensively studied in the literature, verifying stability in stochastic control systems is an open problem. The few existing works on this topic either consider only specialized forms of stochasticity or make restrictive assumptions on the system, rendering them inapplicable to learning algorithms with neural network policies. \r\n In this work, we present an approach for general nonlinear stochastic control problems with two novel aspects: (a) instead of classical stochastic extensions of Lyapunov functions, we use ranking supermartingales (RSMs) to certify a.s. asymptotic stability, and (b) we present a method for learning neural network RSMs. \r\n We prove that our approach guarantees a.s. asymptotic stability of the system and\r\n provides the first method to obtain bounds on the stabilization time, which stochastic Lyapunov functions do not.\r\n Finally, we validate our approach experimentally on a set of nonlinear stochastic reinforcement learning environments with neural network policies."}],"publication_status":"published","day":"28","publisher":"Association for the Advancement of Artificial Intelligence","arxiv":1,"oa_version":"Preprint","doi":"10.1609/aaai.v36i7.20695","author":[{"last_name":"Lechner","full_name":"Lechner, Mathias","id":"3DC22916-F248-11E8-B48F-1D18A9856A87","first_name":"Mathias"},{"id":"294AA7A6-F248-11E8-B48F-1D18A9856A87","first_name":"Dorde","orcid":"0000-0002-4681-1699","full_name":"Zikelic, Dorde","last_name":"Zikelic"},{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee"},{"last_name":"Henzinger","full_name":"Henzinger, Thomas A","orcid":"0000-0002-2985-7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A"}],"year":"2022","department":[{"_id":"ToHe"},{"_id":"KrCh"}],"publication_identifier":{"issn":["2159-5399"],"eissn":["2374-3468"],"isbn":["9781577358350"]}},{"oa_version":"Preprint","arxiv":1,"doi":"10.1609/aaai.v34i02.5546","day":"03","publisher":"Association for the Advancement of Artificial Intelligence","department":[{"_id":"ToHe"},{"_id":"KrCh"}],"publication_identifier":{"issn":["2159-5399"],"eissn":["2374-3468"],"isbn":["9781577358350"]},"conference":{"name":"AAAI: Conference on Artificial Intelligence","start_date":"2020-02-07","location":"New York, NY, United States","end_date":"2020-02-12"},"year":"2020","author":[{"last_name":"Avni","full_name":"Avni, Guy","orcid":"0000-0001-5588-8287","id":"463C8BC2-F248-11E8-B48F-1D18A9856A87","first_name":"Guy"},{"first_name":"Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87","last_name":"Ibsen-Jensen","full_name":"Ibsen-Jensen, Rasmus","orcid":"0000-0003-4783-0389"},{"orcid":"0000-0002-1097-9684","full_name":"Tkadlec, Josef","last_name":"Tkadlec","first_name":"Josef","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87"}],"citation":{"ista":"Avni G, Ibsen-Jensen R, Tkadlec J. 2020. All-pay bidding games on graphs. Proceedings of the AAAI Conference on Artificial Intelligence. 34(02), 1798–1805.","mla":"Avni, Guy, et al. “All-Pay Bidding Games on Graphs.” <i>Proceedings of the AAAI Conference on Artificial Intelligence</i>, vol. 34, no. 02, Association for the Advancement of Artificial Intelligence, 2020, pp. 1798–805, doi:<a href=\"https://doi.org/10.1609/aaai.v34i02.5546\">10.1609/aaai.v34i02.5546</a>.","chicago":"Avni, Guy, Rasmus Ibsen-Jensen, and Josef Tkadlec. “All-Pay Bidding Games on Graphs.” <i>Proceedings of the AAAI Conference on Artificial Intelligence</i>. Association for the Advancement of Artificial Intelligence, 2020. <a href=\"https://doi.org/10.1609/aaai.v34i02.5546\">https://doi.org/10.1609/aaai.v34i02.5546</a>.","ama":"Avni G, Ibsen-Jensen R, Tkadlec J. All-pay bidding games on graphs. <i>Proceedings of the AAAI Conference on Artificial Intelligence</i>. 2020;34(02):1798-1805. doi:<a href=\"https://doi.org/10.1609/aaai.v34i02.5546\">10.1609/aaai.v34i02.5546</a>","ieee":"G. Avni, R. Ibsen-Jensen, and J. Tkadlec, “All-pay bidding games on graphs,” <i>Proceedings of the AAAI Conference on Artificial Intelligence</i>, vol. 34, no. 02. Association for the Advancement of Artificial Intelligence, pp. 1798–1805, 2020.","apa":"Avni, G., Ibsen-Jensen, R., &#38; Tkadlec, J. (2020). All-pay bidding games on graphs. <i>Proceedings of the AAAI Conference on Artificial Intelligence</i>. New York, NY, United States: Association for the Advancement of Artificial Intelligence. <a href=\"https://doi.org/10.1609/aaai.v34i02.5546\">https://doi.org/10.1609/aaai.v34i02.5546</a>","short":"G. Avni, R. Ibsen-Jensen, J. Tkadlec, Proceedings of the AAAI Conference on Artificial Intelligence 34 (2020) 1798–1805."},"type":"journal_article","article_type":"original","status":"public","language":[{"iso":"eng"}],"publication_status":"published","abstract":[{"lang":"eng","text":"In this paper we introduce and study all-pay bidding games, a class of two player, zero-sum games on graphs. The game proceeds as follows. We place a token on some vertex in the graph and assign budgets to the two players. Each turn, each player submits a sealed legal bid (non-negative and below their remaining budget), which is deducted from their budget and the highest bidder moves the token onto an adjacent vertex. The game ends once a sink is reached, and Player 1 pays Player 2 the outcome that is associated with the sink. The players attempt to maximize their expected outcome. Our games model settings where effort (of no inherent value) needs to be invested in an ongoing and stateful manner. On the negative side, we show that even in simple games on DAGs, optimal strategies may require a distribution over bids with infinite support. A central quantity in bidding games is the ratio of the players budgets. On the positive side, we show a simple FPTAS for DAGs, that, for each budget ratio, outputs an approximation for the optimal strategy for that ratio. We also implement it, show that it performs well, and suggests interesting properties of these games. Then, given an outcome c, we show an algorithm for finding the necessary and sufficient initial ratio for guaranteeing outcome c with probability 1 and a strategy ensuring such. Finally, while the general case has not previously been studied, solving the specific game in which Player 1 wins iff he wins the first two auctions, has been long stated as an open question, which we solve."}],"quality_controlled":"1","page":"1798-1805","publication":"Proceedings of the AAAI Conference on Artificial Intelligence","external_id":{"arxiv":["1911.08360"]},"date_created":"2021-02-25T09:05:18Z","_id":"9197","project":[{"call_identifier":"FWF","_id":"25F2ACDE-B435-11E9-9278-68D0E5697425","grant_number":"S11402-N23","name":"Rigorous Systems Engineering"},{"name":"The Wittgenstein Prize","call_identifier":"FWF","_id":"25F42A32-B435-11E9-9278-68D0E5697425","grant_number":"Z211"},{"_id":"264B3912-B435-11E9-9278-68D0E5697425","grant_number":"M02369","call_identifier":"FWF","name":"Formal Methods meets Algorithmic Game Theory"}],"month":"04","title":"All-pay bidding games on graphs","date_updated":"2023-09-05T12:40:00Z","article_processing_charge":"No","date_published":"2020-04-03T00:00:00Z","scopus_import":"1","volume":34,"intvolume":"        34","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","issue":"02","acknowledgement":"This research was supported by the Austrian Science Fund (FWF) under grants S11402-N23 (RiSE/SHiNE), Z211-N23 (Wittgenstein Award), and M 2369-N33 (Meitner fellowship)."},{"department":[{"_id":"FrLo"}],"publication_identifier":{"isbn":["9781577358350"],"eissn":["2374-3468"]},"year":"2020","conference":{"name":"AAAI: Conference on Artificial Intelligence","location":"New York, NY, United States","start_date":"2020-02-07","end_date":"2020-02-12"},"author":[{"full_name":"Locatello, Francesco","orcid":"0000-0002-4850-0683","last_name":"Locatello","id":"26cfd52f-2483-11ee-8040-88983bcc06d4","first_name":"Francesco"},{"first_name":"Stefan","last_name":"Bauer","full_name":"Bauer, Stefan"},{"full_name":"Lucic, Mario","last_name":"Lucic","first_name":"Mario"},{"first_name":"Gunnar","full_name":"Rätsch, Gunnar","last_name":"Rätsch"},{"full_name":"Gelly, Sylvain","last_name":"Gelly","first_name":"Sylvain"},{"last_name":"Schölkopf","full_name":"Schölkopf, Bernhard","first_name":"Bernhard"},{"first_name":"Olivier","last_name":"Bachem","full_name":"Bachem, Olivier"}],"oa_version":"Preprint","arxiv":1,"doi":"10.1609/aaai.v34i09.7120","day":"28","publisher":"Association for the Advancement of Artificial Intelligence","status":"public","language":[{"iso":"eng"}],"abstract":[{"lang":"eng","text":"The goal of the unsupervised learning of disentangled representations is to\r\nseparate the independent explanatory factors of variation in the data without\r\naccess to supervision. In this paper, we summarize the results of Locatello et\r\nal., 2019, and focus on their implications for practitioners. We discuss the\r\ntheoretical result showing that the unsupervised learning of disentangled\r\nrepresentations is fundamentally impossible without inductive biases and the\r\npractical challenges it entails. Finally, we comment on our experimental\r\nfindings, highlighting the limitations of state-of-the-art approaches and\r\ndirections for future research."}],"publication_status":"published","quality_controlled":"1","citation":{"apa":"Locatello, F., Bauer, S., Lucic, M., Rätsch, G., Gelly, S., Schölkopf, B., &#38; Bachem, O. (2020). A commentary on the unsupervised learning of disentangled representations. In <i>The 34th AAAI Conference on Artificial Intelligence</i> (Vol. 34, pp. 13681–13684). New York, NY, United States: Association for the Advancement of Artificial Intelligence. <a href=\"https://doi.org/10.1609/aaai.v34i09.7120\">https://doi.org/10.1609/aaai.v34i09.7120</a>","short":"F. Locatello, S. Bauer, M. Lucic, G. Rätsch, S. Gelly, B. Schölkopf, O. Bachem, in:, The 34th AAAI Conference on Artificial Intelligence, Association for the Advancement of Artificial Intelligence, 2020, pp. 13681–13684.","ieee":"F. Locatello <i>et al.</i>, “A commentary on the unsupervised learning of disentangled representations,” in <i>The 34th AAAI Conference on Artificial Intelligence</i>, New York, NY, United States, 2020, vol. 34, no. 9, pp. 13681–13684.","ama":"Locatello F, Bauer S, Lucic M, et al. A commentary on the unsupervised learning of disentangled representations. In: <i>The 34th AAAI Conference on Artificial Intelligence</i>. Vol 34. Association for the Advancement of Artificial Intelligence; 2020:13681-13684. doi:<a href=\"https://doi.org/10.1609/aaai.v34i09.7120\">10.1609/aaai.v34i09.7120</a>","chicago":"Locatello, Francesco, Stefan Bauer, Mario Lucic, Gunnar Rätsch, Sylvain Gelly, Bernhard Schölkopf, and Olivier Bachem. “A Commentary on the Unsupervised Learning of Disentangled Representations.” In <i>The 34th AAAI Conference on Artificial Intelligence</i>, 34:13681–84. Association for the Advancement of Artificial Intelligence, 2020. <a href=\"https://doi.org/10.1609/aaai.v34i09.7120\">https://doi.org/10.1609/aaai.v34i09.7120</a>.","ista":"Locatello F, Bauer S, Lucic M, Rätsch G, Gelly S, Schölkopf B, Bachem O. 2020. A commentary on the unsupervised learning of disentangled representations. The 34th AAAI Conference on Artificial Intelligence. AAAI: Conference on Artificial Intelligence vol. 34, 13681–13684.","mla":"Locatello, Francesco, et al. “A Commentary on the Unsupervised Learning of Disentangled Representations.” <i>The 34th AAAI Conference on Artificial Intelligence</i>, vol. 34, no. 9, Association for the Advancement of Artificial Intelligence, 2020, pp. 13681–84, doi:<a href=\"https://doi.org/10.1609/aaai.v34i09.7120\">10.1609/aaai.v34i09.7120</a>."},"type":"conference","month":"07","title":"A commentary on the unsupervised learning of disentangled representations","date_updated":"2023-09-12T07:44:48Z","article_processing_charge":"No","date_published":"2020-07-28T00:00:00Z","page":"13681-13684","publication":"The 34th AAAI Conference on Artificial Intelligence","external_id":{"arxiv":["2007.14184"]},"date_created":"2023-08-22T14:07:26Z","_id":"14186","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2007.14184"}],"volume":34,"intvolume":"        34","oa":1,"issue":"9","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","extern":"1","scopus_import":"1"}]