Multiplicative Rewards in Markovian Models

anonymous, Christel Baier, Krishnendu Chatterjee, Tobias Meggendorfer, Jakob Piribauer · 2025

Read Multiplicative Rewards in Markovian Models by anonymous, Christel Baier, Krishnendu Chatterjee, Tobias Meggendorfer, Jakob Piribauer (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-18277.txt.

Introduction

Christel Baier, Krishnendu Chatterjee, Tobias Meggendorfer, and Jakob Piribauer study rewards that multiply rather than add in a 2025 paper. Their setting is Markov models, which describe systems that jump between states by chance or by choice. In most work, rewards from each step are summed; here they are multiplied together.

That change alters the math in deep ways. The expected value can blow up to infinity even through states visited only once. The authors map how hard each version of the problem is to compute, for plain chains and for models with choices. Some cases are solvable fast, others need vast space, and one key case rests on open number theory questions. Special cases where an end state is surely reached are fully tractable.

Catalog record

CREATORanonymous, Christel Baier, Krishnendu Chatterjee, Tobias Meggendorfer, Jakob Piribauer
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE119 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-18277

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Multiplicative Rewards in Markovian Models anonymous, Christel Baier, Krishnendu Chatterjee, Tobias Meggendorfer, Jakob Piribauer Abstract This paper studies the expected value of multiplicative rewards , where rewards obtained in each step are multiplied (instead of the usual addition), in Markov chains (MCs) and Markov decision processes (MDPs). One of the key differences to additive rewards is that the expected value may diverge to ∞ \infty not only due to recurrent, but also due to transient states. For MCs, computing the value is shown to be possible in polynomial time given an oracle for the comparison of succinctly represented integers (CSRI), which is only known to be solvable in polynomial time subject to number-theoretic conjectures. Interestingly, distinguishing whether the value is ∞ \infty or 0 0 is at least as hard as CSRI, while determining if it is one of these two can be done in polynomial time. In MDPs, the optimal value can be computed in polynomial space. Further refined complexity results and results on the complexity of optimal schedulers are presented. The techniques developed for MDPs additionally allow to solve the multiplicative variant of the stochastic shortest path problem. Finally, for MCs and MDPs where an absorbing state is reached almost surely, all considered problems are solvable in polynomial time. I Introduction Markov chains are standard models for the analysis and verification of systems exhibiting probabilistic behavior. Markov decision processes (MDPs) extend Markov chains with non-determinism and are widely used in various fields of science such as computer science [ 28 ] , biology [ 27 ] , epidemiology [ 17 ] , and chemistry [ 16 ] , to name a few. In computer science, MDPs play a crucial role in formal verification [ 6 ] , control theory, and artificial intelligence, e.g., as the underlying model for reinforcement learning [ 20 ] , among others. In a nutshell, an MDP works as follows: In each state of an MDP, a so-called scheduler chooses from a set of available actions. Afterwards, the successor state is chosen randomly according to a probability distribution associated with the chosen action. Once a scheduler is fixed, the process is purely probabilistic. Rewards To model quantitative aspects of a system such as runtime, energy consumption, or utility, Markov chains and MDPs can be equipped with reward structures. In MDPs, the central arising problem is finding a scheduler optimizing the expected value of the obtained reward. The most prominent reward mechanisms are accumulated/total (additive) rewards (rewards obtained in each step are summed up), discounted accumulated rewards (rewards obtained after n steps are discounted with factor \lambda^{n} for \lambda\in(0,1) ), and mean payoff (average reward accumulated per step). Optimizing the expected values of these quantities has extensively been studied for decades (see, e.g., [ 28 ] ) and is doable in polynomial time. Multiplicative rewards This paper investigates multiplicative rewards in Markov chains and MDPs. Instead of adding up rewards obtained in each step, the rewards are simply multiplied. Typical situations in which rewards behave multiplicatively arise whenever the change of some quantity is proportional to the amount already obtained. This is a common theme in chemical and biological systems where, e.g., the current rate of a reaction or the change of the size of a population is proportional to the current concentration of a substance or the current population size. Also in financial settings, multiplicative rewards naturally occur. The return of an investment depends on the interest rate as well as the current size of the investment. Example I.1 . Suppose a plant population decreases or increases yearly depending on the climatic conditions during the year. Favorable climatic conditions lead to a 30\% increase of the population while adverse conditions lead to a 25\% decrease. Further suppose both conditions are equally likely each year. We can model this with a simple Markov chain with multiplicative rewards as shown in Figure 1 . Starting with good climate, in each step there is a 0.5 probability to move to the good state and 0.5 probability to move to the bad state. Along the resulting path, the rewards 1.3 and 0.75 (denoted in the states) are obtained and multiplied together. In this case, the expected multiplicative reward over an infinite time horizon is 0 due to the negative logarithmic mean payoff of 0.5\cdot\log(1.3)+0.5\cdot\log(0.75)=0.5\cdot\log(0.975)<0 . In particular, this means the plant population will become extinct. good, 1.3 bad, 0.75 0.5 0.5 0.5 0.5 Figure 1: A Markov chain modelling a plant population. Exponential utility functions A further situation in which multiplicative rewards naturally occur is the use of exponential utility functions , a type of utility function frequently used in economics and suitable to express risk-aversion . Applied to the maximization of additive rewards in MDPs, this works as follows. If the additive reward along an execution is w , the associated utility is f(w)=1-2^{-\lambda w} for a fixed parameter \lambda>0 . This monotone function ensures that high rewards lead to a high utility. But the change in utility decreases for higher rewards. Low outcomes, however, have a strong effect on the utility and should be avoided. A scheduler maximizing the expected exponential utility hence has to ensure high values of the additive rewards while keeping the probability of low outcomes small. The use of the exponential utility function incentivizes a risk-averse behavior. An exponential utility function converts the additive reward mechanism into a multiplicative one: If the rewards w_{1},w_{2},\dots are collected on a run of the MDP leading to an additive reward of w=w_{1}+w_{2}+\dots , the exponential utility f(w) can be obtained as 1-f(w_{1})\cdot f(w_{2})\cdot\dots . So, maximizing the expected utility is the same as minimizing the expected multiplicative rewards after transforming the reward r(s) of a state s to f(r(s)) . Hence, the optimization of multiplicative rewards studied in this paper can be used for the risk-averse optimization of additive rewards. Such an exponential utility function also lies at the heart of the entropic risk measure [ 15 ] . This notion has been widely studied in finance and operation research (see, e.g., [ 14 , 9 ] ). For Markovian models, more precisely Markov chains, MDPs, as well as stochastic games extending MDPs with a second player, the optimization of the entropic risk measure applied to additive non-negative rewards has been studied in [ 5 ] . Divergence in recurrent and transient states One noteworthy difference between additive and multiplicative rewards is as follows. In Markov chains, the expected value of accumulated additive rewards can only diverge to \infty due to the rewards collected at recurrent states. These are states that are visited infinitely often with positive probability. In contrast, the expected value of multiplicative rewards may additionally be infinite due to rewards collected at transient states, i.e. states that are almost surely only visited finitely often. Example I.2 . Consider the Markov chain \mathsf{M} depicted in Figure 2 . From the initial state s_{1} , the Markov chain loops back to s_{1} or moves to the absorbing state s_{2} with probability 1/2 each. The state s_{1} is hence visited twice in expectation and almost surely only finitely often. As soon as s_{2} is reached, reward 1 is obtained in every step not influencing the

Read the complete text