{"entities":{"Q805501":{"pageid":807349,"ns":120,"title":"Item:Q805501","lastrevid":64473549,"modified":"2026-04-11T20:06:59Z","type":"item","id":"Q805501","labels":{"en":{"language":"en","value":"Denumerable state nonhomogeneous Markov decision processes"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4204141"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805501$90EDC533-F808-4862-BD0C-96C21A8F9A90","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"93424dd9b290fe4b74d131d5b844622eb0adc63c","datavalue":{"value":{"text":"Denumerable state nonhomogeneous Markov decision processes","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q805501$824D6C85-12DE-4284-B7EC-2A74F0E55D17","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1d7603e2414f8d974cdc77609d049bdaa8358842","datavalue":{"value":"0728.90087","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q805501$D1167C6D-5104-4EE6-B918-4475D9283390","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"40bdd53e36598e2f772e78107bf6d6e0b9ca9227","datavalue":{"value":"10.1016/0022-247X(90)90265-H","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q805501$36AFAA13-03AF-4273-8E57-54DB533B7154","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d0c19767aa2c6ca4b0daf93864bbea4c2f4ce4d5","datavalue":{"value":{"entity-type":"item","numeric-id":341467,"id":"Q341467"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805501$CCEFFE8E-0C80-449C-93B8-EF416C35C596","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8b572e7311b89381df8898098e1b464af6558e92","datavalue":{"value":{"entity-type":"item","numeric-id":200435,"id":"Q200435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805501$5359E330-5461-44F6-BA8A-3213F4E2E532","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3d6909d519daff13c846ee3c5786c88cf823ecb9","datavalue":{"value":{"entity-type":"item","numeric-id":1731747,"id":"Q1731747"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805501$48ABCBE8-2D4D-4A66-ACB2-EE1E030C9DD3","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"c5ad7b9baf8e531c6b1ad954eb5f2899cc8fe5e5","datavalue":{"value":{"entity-type":"item","numeric-id":85344,"id":"Q85344"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805501$FFD7F4E8-044A-464A-AE6A-8A1E78CA0F9F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q805501$C770E5F1-BF8B-47B7-870E-B44213F38230","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8a7b989557a067f4c8c94ac00fcfe0e91cd7d1b0","datavalue":{"value":"The framework for this paper is: a denumerable number of states, \\(\\{\\) \\(i\\}\\) ; an infinite number of decision stages, \\(\\{\\) \\(k\\}\\) ; a finite set of actions, \\(\\{x^ i_ k\\}\\) for each i and k, and a set of infinite horizon strategies \\(\\{\\) \\(x\\}\\), whose k-th member is a policy k; a set of transition probability matrices \\(\\{P_ k(x_ k)\\}\\); a set of immediate reward vectors \\(\\{R_ k(x_ k)\\}\\); a discount factor \\(0\\leq \\alpha \\leq 1\\); a set of expected discounted reward vectors, \\(\\{V_ 0(x,N)\\}\\) covering the first N decision stages if strategy x (a finite strategy, x(N), truncated to the first N decision stages) is used.    Discount \\((\\alpha <1)\\) and average \\((\\alpha =1\\), lim.inf) optimality are defined for \\(N\\to \\infty\\). A strategy, \\(x^*\\), is algorithmically optimal, if there is a sequence \\(\\{N_ m\\}\\) such that \\(\\{x^*(N_ m)\\}\\) (i.e. optimal \\(N_ m\\)-stage strategies) converge to \\(x^*\\) in the topology induced by a specified metric p(.,.). The paper deals with algorithmic optimality and its relationship with other constructs. Various assumptions are made and each result is governed by some of these assumptions.    Theorem 1 demonstrates the existence of algorithmically optimal strategies. Theorem 2 demonstrates that algorithmic optimality implies discount optimality. Theorem 5 demonstrates that algorithmic optimality implies average optimality. Theorem 6 demonstrates that an algorithmically optimal strategy is unique if and only if \\(\\{x^*(N)\\}\\) converges to \\(x^*\\), in the topology induced by the p(.,.) metric, for all choices of \\(\\{x^*(N)\\}.\\)    Finally, using relative values, solution horizon extensions of some earlier work are given, in terms of algorithmic optimality, and an algorithm is given for finding, in a finite number of iterations, a first policy, \\(x^*_ 0\\), of an algorithmically optimal strategy \\(x^*\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q805501$62B3ED8B-9D11-4477-AFB3-4E2B0C3169D2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"377d3ab03372cff12915e0de0374438ff70c3716","datavalue":{"value":"90C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q805501$CF120AA3-63EE-4696-A470-90BA7710C403","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0eb2e646817f74ef5fe3a3737bd30069cb81f8f7","datavalue":{"value":"4204141","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q805501$B2FDAB21-37F0-42C7-84AB-D394F6AD5E8A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d8b149c40470692ee76a2923db5969ebd633302b","datavalue":{"value":"denumerable number of states","type":"string"},"datatype":"string"},"type":"statement","id":"Q805501$571EF009-07F5-46BE-929B-D34001C7E869","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a9ef2f6e1b6c69dce71c15a323b328d8b9b8df93","datavalue":{"value":"infinite number of decision stages","type":"string"},"datatype":"string"},"type":"statement","id":"Q805501$70335D63-F255-4EBC-BCFE-42CBDB1AD9CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a244378f53d9afd70a3f78a7bdc478b19c0441b6","datavalue":{"value":"finite set of actions","type":"string"},"datatype":"string"},"type":"statement","id":"Q805501$4C4DA420-3AF9-4CDD-BFDD-1911325DC6BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a24ebb8368be8d86217a2dfd0faf23a1a7d4d4b6","datavalue":{"value":"infinite horizon strategies","type":"string"},"datatype":"string"},"type":"statement","id":"Q805501$82024E2A-EEA9-40EC-8461-C0A30C73B5B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"712b497a3438915cd49e0291385c216fc0bd3475","datavalue":{"value":"algorithmic optimality","type":"string"},"datatype":"string"},"type":"statement","id":"Q805501$1CE48131-B62A-40B9-A92E-94EF8FE186B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f4ce566f5445a5d24494a7e948b08068a63ffae0","datavalue":{"value":"algorithmically optimal strategies","type":"string"},"datatype":"string"},"type":"statement","id":"Q805501$50BBEEF7-0EE1-40A3-AA26-966B87DC228F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f49946e7d39046d8223c7a902761e22d0eeaeae1","datavalue":{"value":"solution horizon extensions","type":"string"},"datatype":"string"},"type":"statement","id":"Q805501$4630D440-A8A2-4541-B31D-CC8034D0B08C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"220e78837b2cafebe466a8a108312f61f409efae","datavalue":{"value":{"entity-type":"item","numeric-id":181183,"id":"Q181183"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805501$B873177B-7593-4ADE-BA78-7E18642AB22D","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805501$3C7042DA-0077-4052-9260-20A3B6EA22D0","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac1d44f3aba4be0332c7689ffaa4905d7ebf328b","datavalue":{"value":{"entity-type":"item","numeric-id":3347585,"id":"Q3347585"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805501$D257EB84-4CC6-48B5-B2C4-AFC349507A02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7efc40158246a76044cf738d6f68d0a2a7fa120d","datavalue":{"value":{"entity-type":"item","numeric-id":1062029,"id":"Q1062029"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805501$0FCA5CCD-A31D-4EF3-9322-5A6B7DB80BEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b402f91583dc53146ab82bbed0089220601f08de","datavalue":{"value":{"entity-type":"item","numeric-id":1194211,"id":"Q1194211"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805501$F2B32E0C-D3CF-4AC3-AD69-9A661F9121B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2469d5ab3a820ed397bb5ff822fbac7c077580bc","datavalue":{"value":{"entity-type":"item","numeric-id":1250794,"id":"Q1250794"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805501$93DE102D-0F12-4672-92E7-928357C49EA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"742e7d8ada88ca00f56e004ceb4a87393d5ba5de","datavalue":{"value":{"entity-type":"item","numeric-id":1104254,"id":"Q1104254"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805501$F173E096-54F5-4920-9F80-ED3E8D0F3E98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e08caed69c87795f8c49b6826c441ef0ce2a3979","datavalue":{"value":{"entity-type":"item","numeric-id":3206683,"id":"Q3206683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805501$A8460EAE-5F19-47DC-B83C-A98455247103","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"98383625b260f09800cc5df79755f26fdb14e812","datavalue":{"value":{"entity-type":"item","numeric-id":4729637,"id":"Q4729637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805501$21ADFC89-099F-4682-9E80-86463DA4068A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0ddc890dd519ae4dbc58ca5f3ca2d197e15416cb","datavalue":{"value":{"entity-type":"item","numeric-id":3796986,"id":"Q3796986"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805501$5E304495-05A7-42BF-BF87-3D7F46B64681","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc26ccab26ff53237b1d744d3b0adf202278f6cf","datavalue":{"value":{"entity-type":"item","numeric-id":5663172,"id":"Q5663172"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805501$BE087CC7-1636-497B-9962-CC0614F72A0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a0b843dcba46b86965b26f3a108e36829d8fd04","datavalue":{"value":{"entity-type":"item","numeric-id":5540144,"id":"Q5540144"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805501$9752F4B2-CE57-45F2-B78F-A54D33578170","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e93bfa11d83eec2c1627fbac8bf082162bf483a8","datavalue":{"value":{"entity-type":"item","numeric-id":3990571,"id":"Q3990571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805501$BC817689-1321-4F79-99D3-38DFDF5912EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f35a3e2dc91a38ba53d55e474f9c9d5060c9745d","datavalue":{"value":{"entity-type":"item","numeric-id":5538315,"id":"Q5538315"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805501$1977FEAC-2BB8-4331-B97F-60E34E9F799C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b8fa07943c21755cde5f9bd5b4fccc6440a3a541","datavalue":{"value":{"entity-type":"item","numeric-id":1299921,"id":"Q1299921"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c324870226cf545758451c911f249eeb724bc962","datavalue":{"value":{"amount":"+0.9155767","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q805501$470E25A7-FB79-44FD-B8F5-51AB13C77037","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8d9b0f5f73a0f5b4671463a227ac63c6d7a81d91","datavalue":{"value":{"entity-type":"item","numeric-id":5179601,"id":"Q5179601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4c6902b9bf90ad604b53249b92638bbd13d0cf83","datavalue":{"value":{"amount":"+0.905528","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q805501$D59B021B-7285-4231-BD00-5332921F1846","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c870b97278549af61e58d65324ebc70da5380097","datavalue":{"value":{"entity-type":"item","numeric-id":3153648,"id":"Q3153648"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bb135d379ce0ae3b7763cdea8d1bb07a9c4c9a0d","datavalue":{"value":{"amount":"+0.8989042","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q805501$F9801F58-A10D-4ABC-B59C-3B64BB5A492B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6dfc40fa276ad3d2240e190cf9d8d7bf36a9e135","datavalue":{"value":{"entity-type":"item","numeric-id":4534402,"id":"Q4534402"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"201a5821ade751f71cb900e01e9b5aed4dabe1c6","datavalue":{"value":{"amount":"+0.8987421","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q805501$0364D08E-6B04-420F-94C3-EACEECE21BA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4f4fda1bff5021f331f8ac5059d3a78738e420c3","datavalue":{"value":{"entity-type":"item","numeric-id":1085078,"id":"Q1085078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"afeb90f7fe58fccde00406e37f4b8776ac7847d3","datavalue":{"value":{"amount":"+0.89218825","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q805501$35CB0226-D3DB-41E4-8012-24A84734F471","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"449b945937f24c05f6d85bb63f0dd363bf384330","datavalue":{"value":{"entity-type":"item","numeric-id":3360681,"id":"Q3360681"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e47d12847bc56e857923f99a6d487d0d30e6f02b","datavalue":{"value":{"amount":"+0.88197803","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q805501$62C5E2E5-3106-407A-AFE1-E032EDEEFA41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"823ca4134915a7bcadd951ddcafcef5b8ba58f77","datavalue":{"value":{"entity-type":"item","numeric-id":1079512,"id":"Q1079512"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1c458dc78f1d432b0682c28f11ece3bedb3c76dd","datavalue":{"value":{"amount":"+0.8805452","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q805501$41A04C8D-9A9F-45C3-A669-8A20F927CA1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5f8bbe3d277f9f8317ac371f8d0e45d711a9833b","datavalue":{"value":{"entity-type":"item","numeric-id":1378679,"id":"Q1378679"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1042b72f1e68591e9bd72564b73b9c58809c9d30","datavalue":{"value":{"amount":"+0.8801638","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q805501$8F76D567-33A5-4351-950C-45FF5AC1FAE7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Denumerable state nonhomogeneous Markov decision processes","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Denumerable_state_nonhomogeneous_Markov_decision_processes"}}}}}