Multi-agent systems comprise entities whose individual decision making behavior may depend on one another's. Game-theory provides apposite concepts to reason in a math.matically precise fashion about such interact...
详细信息
Multi-agent systems comprise entities whose individual decision making behavior may depend on one another's. Game-theory provides apposite concepts to reason in a math.matically precise fashion about such interactive and interdependent situations. This paper concerns a logical analysis of the game-theoretical notions of Nash equilibrium and its subgame perfect variety as they apply to a particular class of extensive games of perfect information. Extensive games are defined as a special type of labelled graph and we argue that modal languages can be employed in their description. We propose a logic for a multi-modal language and prove its completeness with respect to a class of frames that correspond with a particular class of extensive games. In this multimodal language (subgame perfect) Nash equilibria can be characterized. Finally, we show how this approach can formally be refined by using Prepositional Dynamic Logic (PDL), though we leave completeness as an open question.
We present metric-E3, a provably near-optimal algorithm for reinforcement learning in Markov decision processes in which there is a natural metric on the state space that allows the construction of accurate local mode...
详细信息
ISBN:
(纸本)1577351894
We present metric-E3, a provably near-optimal algorithm for reinforcement learning in Markov decision processes in which there is a natural metric on the state space that allows the construction of accurate local models. The algorithm is a generalization of the E3 algorithm of Kearns and Singh, and assumes a black box for approximate planning. Unlike the original E3, metric-E3 finds a near optimal policy in an amount of time that does not directly depend on the size of the state space, but instead depends on the covering number of the state space. Informally, the covering number is the number of neighborhoods required for accurate local modeling.
Soil apparent electrical conductivity (EC) as measured by electromagnetic induction (EM) using the Geonics® EM-38 has shown promise as a soil survey tool in Iowa and other parts of the American Midwest. Surveys m...
详细信息
Soil apparent electrical conductivity (EC) as measured by electromagnetic induction (EM) using the Geonics® EM-38 has shown promise as a soil survey tool in Iowa and other parts of the American Midwest. Surveys made with the EM-38 often take place in the fall after harvest or in the spring prior to planting. Because of this, and because use of conservation tillage and other techniques that leave crop residues on the soil surface is prevalent in many parts of the United States, it is common for fields to have crop residues covering the soil surface when EM surveys are conducted. These residues might alter the soil EC values obtained with the EM-38. To test this possibility, soil EC was determined at two sites with three different types of residue cover (corn (Zea mays L.), soybeans (Glycine max L.), and durum wheat (Triticum turgidum L.)). The residue cover at each site was then brushed aside, and the soil EC was determined with bare ground exposed to the EM-38. On average, soil EC readings were 0.2 mS/m higher when the EM-38 was exposed to bare ground, and 68% of the bare ground readings were higher than the corresponding readings through crop residues. However, the 0.2 mS/m average difference is not significant when compared to the natural variation found in soil EC readings within any given soil series. Therefore, the results of this study indicate that soil EC values obtained with the EM-38 through crop residues are valid representations of the actual soil EC value.
In order to understand AdaBoost's dynamics, especially its ability to maximize margins, we derive an associated simplified nonlinear iterated map and analyze its behavior in low-dimensional cases. We find stable c...
In order to understand AdaBoost's dynamics, especially its ability to maximize margins, we derive an associated simplified nonlinear iterated map and analyze its behavior in low-dimensional cases. We find stable cycles for these cases, which can explicitly be used to solve for AdaBoost's output. By considering AdaBoost as a dynamical system, we are able to prove Rätsch and Warmuth's conjecture that AdaBoost may fail to converge to a maximal-margin combined classifier when given a 'non-optimal' weak learning algorithm. AdaBoost is known to be a coordinate descent method, but other known algorithms that explicitly aim to maximize the margin (such as AdaBoost* and arc-gv) are not. We consider a differentiable function for which coordinate ascent will yield a maximum margin solution. We then make a simple approximation to derive a new boosting algorithm whose updates are slightly more aggressive than those of arc-gv.
We consider the problem of finding the weight of a Euclidean minimum spanning tree for a set of n points in d. We focus on the situation when the input point set is supported by certain basic (and commonly used) geome...
详细信息
We consider the problem of finding the weight of a Euclidean minimum spanning tree for a set of n points in d. We focus on the situation when the input point set is supported by certain basic (and commonly used) geometric data structures that can provide efficient access to the input in a structured way. We present an algorithm that estimates with high probability the weight of a Euclidean minimum spanning tree of a set of points to within 1 + Ε using only Õ(√n poly(1/Ε)) queries for constant d. The algorithm assumes that the input is supported by a minimal bounding cube enclosing it, by orthogonal range queries, and by cone approximate nearest neighbors queries.
This paper is devoted to numerical analysis of ill-posed problems of evolution equations in Banach spaces. Since a C-semigroup is a regularizator family for an ill posed-problem we consider approximation by C-semigrou...
This paper is devoted to numerical analysis of ill-posed problems of evolution equations in Banach spaces. Since a C-semigroup is a regularizator family for an ill posed-problem we consider approximation by C-semigroups for a general approximation scheme. In this direction the relevant notion is that of C operator, which provides the regularization property. Within this context some interesting aspects of regularization using stochastic differential equations with discretization in space and in time variables are considered.
We present the first explicit construction of Probabilistically Checkable Proofs (PCPs) and Locally Testable Codes (LTCs) of fixed constant query complexity which have almost-linear (= n · 2Õ(√log n) size. ...
详细信息
We present the first explicit construction of Probabilistically Checkable Proofs (PCPs) and Locally Testable Codes (LTCs) of fixed constant query complexity which have almost-linear (= n · 2Õ(√log n) size. Such objects were recently shown to exist (nonconstructively) by Goldreich and Sudan. Previous explicit constructions required size n1+ω(Ε) with 1/Ε queries. The key to these constructions is a nearly optimal randomness-efficient version of the low degree test. In a similar way we give a randomness-efficient version of the BLR linearity test (which is used, for instance, in locally testing the Hadamard code). The derandomizations are obtained through Ε-biased sets for vector spaces over finite fields. The analysis of the derandomized tests rely on alternative views of Ε-biased sets - as generating sets of Cayley expander graphs for the low degree test, and as defining linear error-correcting codes for the linearity test.
This paper investigates time-invariant linear systems subject to input and state constraints. It is shown that the recoverable region (which is the largest domain of attraction that is theoretically achievable) can be...
详细信息
This paper investigates time-invariant linear systems subject to input and state constraints. It is shown that the recoverable region (which is the largest domain of attraction that is theoretically achievable) can be semiglobally stabilized by continuous nonlinear feedbacks while satisfying the constraints. Moreover, a reduction technique is presented which shows, when trying to compute the recoverable region, that we only need to compute the recoverable region for a system of lower dimension which generally leads to a considerable simplification in the computational effort.
The Medium Access Control (MAC) scheme proposed by DAVIC/DVB, IEEE 802.14 and DOCSIS for the upstream channel of Hybrid Fiber Coaxial (HFC) access networks is based on a mixable contention-based/contention-less time s...
详细信息
ISBN:
(纸本)0780377524
The Medium Access Control (MAC) scheme proposed by DAVIC/DVB, IEEE 802.14 and DOCSIS for the upstream channel of Hybrid Fiber Coaxial (HFC) access networks is based on a mixable contention-based/contention-less time slot assignment. Contention-less slots are assigned by the head end to end stations according to a reservation scheme. Contention-based slots are randomly accessed by active terminals without any preliminary allocation, so that collisions may occur. To resolve contention, the contention tree algorithm has been widely accepted by the DVB/DAVIC, IEEE 802.14 and DOCSIS standards for MAC because of higher throughput and lower access delay. In this paper we propose a novel contention resolution mechanism and compare its performance with that of existing procedures. The proposed procedure is termed as static arrival slot mechanism. In this mechanism, one slot in each frame is exclusively reserved for new arrivals that wish to access the channel using contention resolution, and at least one slot is reserved for resolving their contention if there was one in the arrival slot. The performance of the proposed mechanism is evaluated through analysis and simulation. The results show that the proposed mechanism outperforms existing contention resolution procedures under heavy traffic.
We consider array languages (sets of pictures consisting of symbols placed in the lattice points of the 2D grid) and the possibility to handle them with P systems. After proving binary normal forms for array matrix gr...
详细信息
暂无评论