The Experts below are selected from a list of 759 Experts worldwide ranked by ideXlab platform
Dimitri P. Bertsekas - One of the best experts on this subject based on the ideXlab platform.
-
A Mixed Value and Policy Iteration Method for Stochastic Control with Universally Measurable Policies
Mathematics of Operations Research, 2015Co-Authors: Dimitri P. BertsekasAbstract:We consider stochastic optimal control models with Borel spaces and universally measurable policies. For such models the standard policy iteration is known to have difficult measurability issues and cannot be carried out in general. We present a mixed value and policy iteration method that circumvents this difficulty. The method allows the use of stationary policies in computing the optimal cost function in a manner that resembles policy iteration. It can also be used to address similar difficulties of policy iteration in the context of upper and lower semicontinuous models. We analyze the convergence of the method in infinite horizon total cost problems for the discounted case where the one-stage costs are bounded and for the undiscounted case where the one-stage costs are nonpositive or nonnegative. For undiscounted total cost problems with nonnegative one-stage costs, we also give a new convergence theorem for value iteration that shows that value iteration converges whenever it is initialized with a function that is above the optimal cost function and yet bounded by a multiple of the optimal cost function. This condition resembles Whittle’s bridging condition and is partly motivated by it. The theorem is also partly motivated by a result of Maitra and Sudderth that showed that value iteration, when initialized with the constant function zero, could require a Transfinite Number of iterations to converge. We use the new convergence theorem for value iteration to establish the convergence of our mixed value and policy iteration method for the nonnegative cost case.
-
A Mixed Value and Policy Iteration Method for Stochastic Control with Universally Measurable Policies
2014Co-Authors: Dimitri P. BertsekasAbstract:We consider the stochastic control model with Borel spaces and universally measurable policies. For this model the standard policy iteration is known to have difficult measurability issues and cannot be carried out in general. We present a mixed value and policy iteration method that circumvents this difficulty. The method allows the use of stationary policies in computing the optimal cost function, in a manner that resembles policy iteration. It can also be used to address similar difficulties of policy iteration in the context of upper and lower semicontinuous models. We analyze the convergence of the method in infinite horizon total cost problems, for the discounted case where the one-stage costs are bounded, and for the undiscounted case where the one-stage costs are nonpositive or nonnegative. For undiscounted total cost problems with nonnegative one-stage costs, we also give a new convergence theorem for value iteration, which shows that value iteration converges whenever it is initialized with a function that is above the optimal cost function and yet bounded by a multiple of the optimal cost function. This condition resembles Whittle’s bridging condition and is partly motivated by it. The theorem is also partly motivated by a result of Maitra and Sudderth, which showed that value iteration, when initialized with the constant function zero, could require a Transfinite Number of iterations to converge. We use the new convergence theorem for value iteration to establish the convergence of our mixed value and policy iteration method for the nonnegative cost case
Grzegorz Bancerek - One of the best experts on this subject based on the ideXlab platform.
-
DOI:????? Epsilon Numbers and Cantor Normal Form
2015Co-Authors: Grzegorz BancerekAbstract:Summary. An epsilon Number is a Transfinite Number which is a fixed point of an exponential map: ωε = ε. The formalization of the concept is done with use of the tetration of ordinals (Knuth’s arrow notation, ↑↑). Namely, the ordinal indexing of epsilon Numbers is defined as follows: ε0 = ω ↑↑ω, εα+1 = εα ↑↑ω, and for limit ordinal λ: ελ = lim α<λ εα = α<λ εα. Tetration stabilizes at ω: α ↑↑β = α ↑↑ω for α 6 = 0 and β ≥ ω. Every ordinal Number α can be uniquely written as n1ω β1 + n2ω β2 + · · ·+ nkωβk, where k is a natural Number, n1, n2,..., nk are positive integers, and β1> β2>...> βk are ordinal Numbers (βk = 0). This decomposition of α is called th
-
Epsilon Numbers and Cantor normal form
2015Co-Authors: Grzegorz BancerekAbstract:Summary. An epsilon Number is a Transfinite Number which is a fixed point of an exponential map: ωε = ε. The formalization of the concept is done with use of the tetration of ordinals (Knuth’s arrow notation, ↑↑). Namely, the ordinal indexing of epsilon Numbers is defined as follows: ε0 = ω ↑↑ω, εα+1 = εα ↑↑ω, and for limit ordinal λ: ελ = lim α<λ εα = α<λ εα. Tetration stabilizes at ω: α ↑↑β = α ↑↑ω for α 6 = 0 and β ≥ ω. Every ordinal Number α can be uniquely written as n1ω β1 + n2ω β2 + · · ·+ nkωβk, where k is a natural Number, n1, n2,..., nk are positive integers, and β1> β2>...> βk are ordinal Numbers (βk = 0). This decomposition of α is called th
-
Epsilon Numbers and Cantor Normal Form
Formalized Mathematics, 2009Co-Authors: Grzegorz BancerekAbstract:An epsilon Number is a Transfinite Number which is a fixed point of an exponential map: ωϵ = ϵ. The formalization of the concept is done with use of the tetration of ordinals (Knuth's arrow notation, ↑). Namely, the ordinal indexing of epsilon Numbers is defined as follows: and for limit ordinal λ: Tetration stabilizes at ω: Every ordinal Number α can be uniquely written as where κ is a natural Number, n1, n2, …, nk are positive integers, and β1 > β2 > … > βκ are ordinal Numbers (βκ = 0). This decomposition of α is called the Cantor Normal Form of α.Białystok Technical University, PolandGrzegorz Bancerek. The fundamental properties of natural Numbers. Formalized Mathematics, 1(1):41-46, 1990.Grzegorz Bancerek. Increasing and continuous ordinal sequences. Formalized Mathematics, 1(4):711-714, 1990.Grzegorz Bancerek. König's theorem. Formalized Mathematics, 1(3):589-593, 1990.Grzegorz Bancerek. Ordinal arithmetics. Formalized Mathematics, 1(3):515-519, 1990.Grzegorz Bancerek. The ordinal Numbers. Formalized Mathematics, 1(1):91-96, 1990.Grzegorz Bancerek. Sequences of ordinal Numbers. Formalized Mathematics, 1(2):281-290, 1990.Czesław Byliński. Functions and their basic properties. Formalized Mathematics, 1(1):55-65, 1990.Agata Darmochwał. Finite sets. Formalized Mathematics, 1(1):165-167, 1990.Tetsuya Tsunetou, Grzegorz Bancerek, and Yatsuka Nakamura. Zero-based finite sequences. Formalized Mathematics, 9(4):825-829, 2001.Edmund Woronowicz. Relations and their basic properties. Formalized Mathematics, 1(1):73-83, 1990
Jacqueline Vauzeilles - One of the best experts on this subject based on the ideXlab platform.
-
Ordinals I: Basic notions
Annals of Mathematics and Artificial Intelligence, 1996Co-Authors: Marie C. Ferbus-zanda, Jacqueline VauzeillesAbstract:At the end of the last century, Cantor generalized the notion of natural integer by considering the order structure of integers. According to the idea of “counting more and more”, he introduced Transfinite Numbers over natural Numbers. Thus an ordinal may be simply defined as a natural Number or a Transfinite Number, and ordinal arithmetic extends usual one. The ordinals up to ε_0 can be described in an intuitive way (with 0, 1, ω and the sum, product and exponentiation operations). In contrast, it cannot be done for ordinals beyond ε_0. In order to describe greater ordinals, Veblen introduced a normal functions hierarchy (i.e. strictly increasing and continuous) from ordinals into ordinals. This construction allows us to describe ordinals until Γ_0, using ordinals preceding Γ_0. Therefore, Γ_0 and ε_0 have a similar role if Veblen functions are used for Γ_0 in addition to the previous operations.
-
Ordinals I: Basic notions
Annals of Mathematics and Artificial Intelligence, 1996Co-Authors: Marie C. Ferbus-zanda, Jacqueline VauzeillesAbstract:At the end of the last century, Cantor generalized the notion of natural integer by considering the order structure of integers. According to the idea of “counting more and more”, he introduced Transfinite Numbers over natural Numbers. Thus an ordinal may be simply defined as a natural Number or a Transfinite Number, and ordinal arithmetic extends usual one. The ordinals up to e0 can be described in an intuitive way (with 0, 1, ω and the sum, product and exponentiation operations). In contrast, it cannot be done for ordinals beyond e0. In order to describe greater ordinals, Veblen introduced a normal functions hierarchy (i.e. strictly increasing and continuous) from ordinals into ordinals. This construction allows us to describe ordinals until Γ0, using ordinals preceding Γ0. Therefore, Γ0 and e0 have a similar role if Veblen functions are used for Γ0 in addition to the previous operations.
-
Ordinals I: basic notions
Annals of Applied Mathematics and Artificial Intelligence, 1996Co-Authors: Jacqueline Vauzeilles, Marie FerbusAbstract:The generalization of the concept of natural integers by means of sum, subtraction, product and quotient successively yielded to the definition of relative integers and subsequently to rational Numbers. Then reals and complexes were introduced. All these constructions result from a study of natural integers which is essentially algebraic. At the end of the last century, Cantor generalized the notion of natural integer by considering the order structure of integers instead of algebraic means. According to the idea of "counting more and more", he introduced Transfinite Numbers over natural Numbers. Thus an ordinal may be simply defined as a natural Number or a Transfinite Number. How can we go beyond the infinite of natural Numbers: we can represent the natural Numbers as points of a semi-line, and juxtapose another semi-line and so on... However this construction can be done for any well-ordered set. Therefore, we will first define well-orderings and show that two well-orderings are always comparable: either these well-orderings are isomorphic or there is an embedding from one to the other. Moreover we will define typical well-ordered sets: ordinals. The isomorphic relation between well-orderings is an equivalence relation and we show that each ordinal is a representant of an equivalence class. Since the collection of all ordinals is itself well-ordered, we can define Transfinite induction on this collection. Actually, finite ordinals are natural Numbers and ordinal arithmetic extends usual one. The ordinals up to epsilon_0 can be described in an intuitive way (with 0, 1, omega and the sum, product and exponentiation operations). In contrast, it cannot be done for ordinals beyond epsilon_0. In order to describe greater ordinals, Veblen, we introduced a normal functions hierarchy (i.e. strictly increasing and continuous) from ordinals into ordinals. This hierarchy is built by taking at each step fixed points of the function defined at the previous step and, at the limit steps, the function which enumerates the common points of the images of the preceding functions. This construction allows us to describe ordinals until Gamma_0, We show how each ordinal smaller than Gamma_0 can be described using ordinals preceding Gamma_0. Therefore Gamma_0 and epsilon_0 have a similar role if Veblen functions are used for Gamma_0 in addition to the previous operations.
Bertsekas, Dimitri P. - One of the best experts on this subject based on the ideXlab platform.
-
A Mixed Value and Policy Iteration Method for Stochastic Control with Universally Measurable Policies
2014Co-Authors: Yu Huizhen, Bertsekas, Dimitri P.Abstract:We consider stochastic control models with Borel spaces and universally measurable policies. For such models the standard policy iteration is known to have difficult measurability issues and cannot be carried out in general. We present a mixed value and policy iteration method that circumvents this difficulty. The method allows the use of stationary policies in computing the optimal cost function, in a manner that resembles policy iteration. It can also be used to address similar difficulties of policy iteration in the context of upper and lower semicontinuous models. We analyze the convergence of the method in infinite horizon total cost problems, for the discounted case where the one-stage costs are bounded, and for the undiscounted case where the one-stage costs are nonpositive or nonnegative. For undiscounted total cost problems with nonnegative one-stage costs, we also give a new convergence theorem for value iteration, which shows that value iteration converges whenever it is initialized with a function that is above the optimal cost function and yet bounded by a multiple of the optimal cost function. This condition resembles Whittle's bridging condition and is partly motivated by it. The theorem is also partly motivated by a result of Maitra and Sudderth, which showed that value iteration, when initialized with the constant function zero, could require a Transfinite Number of iterations to converge. We use the new convergence theorem for value iteration to establish the convergence of our mixed value and policy iteration method for the nonnegative cost case.Comment: Minorly edited from version 2; 60 pages. A shorter version is to appear in the journal Mathematics of Operations Researc
Alessandro Giuliani - One of the best experts on this subject based on the ideXlab platform.
-
Why Systems Biology Can Promote a New Way of Thinking
Systems and Synthetic Biology, 2014Co-Authors: Alessandro GiulianiAbstract:This chapter deals with the effect Systems Biology had on the Nature of what we consider ‘an explanation’ in Biological Science. I try and demonstrate how the most relevant change carried out by Systems Biology approach was the shift from the molecular layer as the definitive place where causative process start to the elucidation of the among elements (at any level of biological organization they are located) interaction network as the main goal of scientific explanations. This change of perspective allows to dissipate a widespread idealistic nightmare looking at the single molecules as Maxwell-demon-like intelligent agents. The recognition that genes work in networks has as consequence the existence of discrete ‘allowed global modes’ of gene expression. This theoretical expectation was verified by the incredibly narrowspace of different tissues (each corresponding to a largely invariant gene expression profile)—around 200 tissue types for all the metazoans emerging from the Transfinite Number of possible combinations of the expression values of around 30,000 genes. This is a crucial step for generating a scientifically sound framework to address global biological regulation.
-
Finding Self-organization from the Dynamic Gene Expressions of Innate Immune Responses
Frontiers in physiology, 2012Co-Authors: Kumar Selvarajoo, Alessandro GiulianiAbstract:It is breathtaking each time to observe the effects of simple social organization of complex systems. Whether watching the display of patterns formed by shoal of fish in an aquarium, or walking down the tropical jungle to witness the synchronized flashing of fireflies, life surrounding us inspires our thinking on the possible mechanisms required to achieve self assembly. Hence, for a long time, mankind has been curious about the mystery of self-organizations. Noticeably, over the years, there have been a large Number of works studying the self-organized behavior in biology. The formation of bio-films by bacteria for survival to environmental changes (Smith and Romesberg, 2007) and the synchronization of neural cells for cognition (Hipp et al., 2011) are good macroscopic examples of collective behaviors. How can one witness such coordination in the realm of molecular biology? One essential feature for self-organized system is to display structure emerging from localized interactions. Obviously, using the traditional approach of monitoring a few intracellular molecules over time does not entail us to notice the existence of patterns or structures. On the other hand, the development of high throughput methodologies has been instrumental in observing the behavior of large Number of molecules. We investigated the whole genome expression (consisting of 22,690 different ORFs from the Affymetrix standard platform) of the innate immune response to the Toll-like receptor (TLR) 4 stimulation (Tsuchiya et al., 2009a). The TLRs, with 10 known members, are “intruder” pattern recognizing proteins found mostly on immune cell surfaces (Kawai and Akira, 2010). The TLR 4, in particular, recognizes lipopolysaccharide (LPS) and triggers the MyD88- and TRIF-dependent pathways (Figure (Figure1A).1A). Hence, the MyD88 and TRIF are crucial for the proper induction of proinflammatory response. Note that the actual TLR 4 pathways are highly complex with several feedback mechanisms, such as the NF-κB regulatory loops and autocrine signaling (Hoffmann et al., 2002; Liu et al., 2008). Figure 1 (A) A highly simplified schematic of TLR4 signaling depicting the primary MyD88-dependent and TRIF/TRAM-dependent pathways (Selvarajoo et al, 2008). (B) Invariance in whole genome Pearson correlation between wildtype 1 h (x-axis) and DKO 1 h ... Our dataset on LPS stimulation of murine macrophages referred to 12 experimental readouts (i.e., four genotypes at three time points): wildtype, MyD88 knock-out (KO), TRIF-KO, and MyD88/TRIF Double KO (DKO) at 0, 1, and 4 h. The common experience of any experimentalist dealing with whole transcriptome data is the fact that any two independent samples of the same cell kind when correlated over 20,000 different gene products will more or less display a near to unity correlation. Our correlation analyses revealed a strong organization, spanning four-order of magnitudes of gene expression levels and encompassing tens of thousands of gene products across all 12 readouts, notwithstanding the huge phenotype macroscopic differences between different samples (e.g., the DKO have their phenotypic immune response abolished; Figure Figure1B).1B). This is a very remarkable fact of nature calling for an explanation and clearly supporting the crucial importance of a thorough investigation of its origin from a statistical mechanics perspective (Conti et al., 2007; Censi et al., 2010). The strong invariance of the transcriptome profiles is a consequence of the existence of very few “attractors” in the gene expression space correspondent to different cell types. The theoretically Transfinite Number of different transcription profiles supported by more than 20,000 different genes each varying over four-order of magnitudes of expression levels drastically collapses to around 200–300 tissue types present in the metazoans (Lima de Faria, 1988). This constrained behavior implies a strongly connected network of gene expression levels endowed with a very few “energy minima” or “allowed states” correspondent to different tissues. The response to acute and transient stimuli (like in our case the response to LPS stimulation by macrophages) does not alter the global attractor organization (Tsuchiya et al., 2009a), on the contrary the response implies a transient dramatic change of very few “responder genes” (growth factors, cytokines in our case), the system then comes back to its “stable state” thanks to the internal constraints between different genes. Turning to temporal correlation analysis, Figure Figure1C1C reports the auto-correlation distribution in time for all the four genotypes relative to the above described choices of genes. In the case of the entire genome (top left), we observe a major departure from unit correlation correspondent to a greater response, as expected, in the case of wildtype. The three mutated genotypes all displayed a very minor, albeit reliable, and monotonically related to time, departure from unity correlation pointing to the “global sensing” of LPS stimulation. The presence of a strong attractor-like structure constraining the genome-wide expression at the cell population level into a sharply defined configuration spanning the entire set of gene expression values allows for only minor departures from unit of the auto-correlation in time, despite the fact that the TLR 4 signaling possesses numerous feedback regulations (Hoffmann et al., 2002; Liu et al., 2008). Shifting to a random choice of 100 genes we observed exactly the same pattern displayed by the entire genome basis (Figure (Figure1C,1C, top right). We iterated many times these random choices and observed a strongly invariant picture starting from a minimal choice of around 80 genes (Tsuchiya et al., 2009a). This is a confirmation of the “scalable” character of gene expression network, or fractality, constituting a strongly connected set whose general connectivity can be appreciated starting from a minimum sample of elements. To summarize, the macroscopic view of temporal gene expressions reveals two distinct mode of innate immune response: (i) the local motion of specific genes responsible for the acute innate immune effect of LPS stimulation is registered by the cytokine choice and, (ii) the global motion of the entire gene regulation network as a connected system. The first is the primarily investigated proinflammatory response that can be modeled using linear response demonstrating the equilibrium state (Selvarajoo et al., 2008; Selvarajoo, 2011). The latter shows the rest of genome, which would otherwise be considered unrelated, is in fact correlated by the complex causality network linking different gene expressions and thus demonstrating self-organized behavior. This emergent pattern does not seem to be dependent of key molecular parameters such as MyD88 and TRIF or in their combined effect, but a signature from global non-equilibrium state of the entire network (Bak and Paczuski, 1995). Notably, the latter state may be crucial for the ability of macrophages to perform its secondary role of coordinated phagocytosis, that is, the removal of necrotic debris of infected cells (Brouckaert et al., 2004). In another relevant work by Nilsson et al. (2006) on TLR4 stimulation, the tracking of 2892 genes over longer periods (up to 24 h) in wildtype macrophages revealed coordinated dynamics among specific clusters of genes that became active at different times. The subnetworks of genes are connected with master or “hub” genes, comprising mainly the well-known transcriptional factors of diverse cellular processes (e.g., ATF-3, NRF-2, ETS) into a scale-free topology, providing means for genomic order of TLR4 response. Pondering deeper into genome character, it has been recently shown for hematopoietic progenitor cell differentiation that gene coregulation move from ordered to disordered and then return to ordered entropy state over several days, through the self-organizing lineage-specific chromosomal networks (Rajapakse et al., 2009). Overall, viewing the whole genome response in entirety and investigating the response of thousands of gene expressions in correlation matrix offers a simple, yet powerful tool to observe and interpret the complex self-organizing nature of living systems. We believe future studies using non-linear approaches and the concept of chaos may elucidate the presence of self-organized criticality to infer “avalanches” of our immune system. As for now, we stress how the traditional distinction between “house-keeping” and “modulated” genes is untenable when in presence of an integrated whole of relations supporting a self-organized behavior.