nils-herrmann/clean_scirepeval huggingface dataset:
Feature-based methods for large scale dynamic programming

We develop a methodological framework and present a few different ways in which dynamic programming and compact representations can be combined to solve large scale stochastic control problems. In particular, we develop algorithms that employ two types of feature-based compact representations; that is, representations that involve feature extraction and a relatively simple approximation architecture. We prove the convergence of these algorithms and provide bounds on the approximation error. As an example, one of these algorithms is used to generate a strategy for the game of Tetris. Furthermore, we provide a counter-example illustrating the difficulties of integrating compact representations with dynamic programming, which exemplifies the shortcomings of certain simple approaches.
A Non-Parametric Approach to Multi-Product Pricing

Developed by General Motors (GM), the Auto Choice Advisor web site (http://www.auto choiceadvisor.com) recommends vehicles to consumers based on their requirements and budget constraints. Through the web site, GM has access to large quantities of data that reflect consumer preferences. Motivated by the availability of such data, we formulate a non-parametric approach to multi-product pricing. We consider a class of models of consumer purchasing behavior, each of which relates observed data on a consumer’s requirements and budget constraint to subsequent purchasing tendencies. To price products, we aim at optimizing prices with respect to a sample of consumer data. We offer a bound on the sample size required for the resulting prices to be near optimal with respect to the true distribution of consumers. The bound exhibits a dependence of O(n log n) on the number n of products being priced, showing that – in terms of sample complexity – the approach is scalable to large numbers of products. With regards to computational complexity, we establish that computing optimal prices with respect to a sample of consumer data is NP-complete in the strong sense. However, when prices are constrained by a price ladder – an ordering of prices defined prior to price determination – the problem becomes one of maximizing a supermodular function with real-valued variables. It is not yet known whether this problem is NP-hard. We provide a heuristic for our price-ladder constrained problem together with encouraging computational results. Finally, we apply our approach to a dataset from the Auto Choice Advisor web site. Our analysis provides insights into the current pricing policy at GM and suggests enhancements that may lead to a more effective pricing strategy. 1School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY, 14853.  paatrus@orie.cornell.edu 2Department of Management Science and Engineering, Stanford University, Stanford, CA, 94305.  bvr@stanford.edu 3Department of Management Science and Engineering, Stanford University, Stanford, CA, 94305.  Saturn L100 (GM) 2nd $18,000 Dodge Stratus SXT Sedan 3rd Chevrolet Malibu Sedan (GM) 4th Mitsubishi Lancer LS 5th Table 1: An example of consumer preference data collected by the ACA web site.
Distributed Optimization in Adaptive Networks

We develop a protocol for optimizing dynamic behavior of a network of simple electronic components, such as a sensor network, an ad hoc network of mobile devices, or a network of communication switches. This protocol requires only local communication and simple computations which are distributed among devices. The protocol is scalable to large networks. As a motivating example, we discuss a problem involving optimization of power consumption, delay, and buffer overflow in a sensor network. 
 
Our approach builds on policy gradient methods for optimization of Markov decision processes. The protocol can be viewed as an extension of policy gradient methods to a context involving a team of agents optimizing aggregate performance through asynchronous distributed communication and computation. We establish that the dynamics of the protocol approximate the solution to an ordinary differential equation that follows the gradient of the performance objective.
Decentralized Protocols for the Optimization of Sensor Networks : Appendix

This paper is motivated by the problem of developing protocols for optimizing the dynamic behavior of networks of simple electronic components, such as a sensor networks. In such networks, protocols must balance multiple, competing criteria such as power consumption, delay, and buffer overflow. Our contribution is to propose a general approach of designing protocols based on policy gradient methods. In addition, this paper offers fundamental contributions to the policy gradient literature. The kind of protocol we propose can be viewed as extending policy gradient methods to a context involving a team of agents optimizing system behavior through asynchronous distributed computation and parsimonious local communication. Our main theoretical contribution is to show that the dynamics of our protocol approximate the solution to an ODE that follows the gradient of the performance objective. Consider a network consisting of a set of components V = {1, . . . , n}. Associated with this network is a discrete-time dynamical system with a finite state space W. Denote the state of the system at timek by w(k), for k = 0, 1, 2, . . .. There aren subsetsW1, . . . , Wn of W, each consisting of states associated with events at component i. At hekth epoch, there are n control actionsa1(k) ∈ A1, . . . , ) ∈ An, where eachAi is a finite set of possible actions that can be taken by component i. The actions are governed by a set of randomized policies π θ1 , . . . , π n θn , parameterized by vectors θ1 ∈ R1 , . . . , θn ∈ Rn. Eachith action process only transitions when the state w(k) transitions to an element of Wi. At the time of transition, the probability thatai(k) becomes anyai ∈ Ai is given byπ θi(ai|w(k)). We assume that (w(k), a(k)) is a Markov chain. While the system is in state w and actiona is applied, each component i receives a reward ri(w, a). The average reward received by the network is r(w, a) = 1 n ∑n i=1 ri(w, a). Given appropriate assumptions (see  for details), we can define the long-term average reward λ(θ) = limK→∞ 1 K E [∑K−1 k=0 r(w(k), a(k)) ] . We wish to find the parameters θ which maximizeλ(θ). We will consider a stochastic approximation iteration θi(k + 1) = θi(k) + χi(k). Here, > 0 is a constant step size and χi(k) is a noisy estimate of the gradient ∇θiλ(θ(k)) computed at component i based on the component’s historically observed states, actions, and rewards, in addition to communication with other components. Our goal is to develop an estimator χi(k) that can be used in an adaptive, asynchronous, and decentralized context, and to establish the convergence of the resulting stochastic approximation scheme.
Neuro-Dynamic Programming: Overview and Recent Trends

Neuro-dynamic programming is comprised of algorithms for solving large-scale stochastic control problems. Many ideas underlying these algorithms originated in the field of artificial intelligence and were motivated to some extent by descriptive models of animal behavior. This chapter provides an overview of the history and state-of-the-art in neuro-dynamic programming, as well as a review of recent results involving two classes of algorithms that have been the subject of much recent research activity: temporal-difference learning and actor-critic methods.
Systeme et procede pour estimer l'emplacement d'un recepteur dans un environnement de trajets multiples

L'invention concerne un systeme et un procede qui permettent de determiner l'emplacement d'un recepteur dans un environnement de trajets multiples. Le signal recu est correle aux signaux de reference associes aux sources d'emission. Chaque fonction de correlation est traitee de facon a deriver divers types de contraintes de signal, tels que des densites de probabilite et des zones ou intervalles d'incertitude. Dans certains modes de realisation, ces contraintes sont destinees aux codes-phases et aux frequences Doppler. Ces contraintes de signal sont transformees en contraintes pour les variables du recepteur, puis fusionnees en une contrainte de recepteur unifiee. Des contraintes a priori, telles que des contraintes portant sur l'emplacement du recepteur ou du horodateur, peuvent etre incorporees dans la contrainte de recepteur unifiee. Dans certains modes de realisation, l'estimation d'un emplacement est fondee sur la frequence Doppler estimee. Les contraintes utilisees par le procede de l'invention sont fondees sur des modeles d'effets par trajets multiples et axees sur l'attenuation de ces effets. Dans un de ces modeles, une densites de probabilite pour le code-phase est obtenue par convolution d'une distribution d'erreur avec une distribution exponentielle decrivant le retard additionnel introduit par trajets multiples. Une autre approche est fondee sur l'identification d'une observation aberrante dans la serie de codes-phases. Dans d'autres approches, les contraintes de zones d'incertitude et les densites de probabilite sont combinees. Le procede de l'invention assure une acquisition des signaux plus rapide et plus sensible, et une localisation plus precise dans l'environnement de trajets multiples, sans inconvenient pour la performance dans d'autres environnements.
Regression methods for pricing complex American-style options

We introduce and analyze a simulation-based approximate dynamic programming method for pricing complex American-style options, with a possibly high-dimensional underlying state space. We work within a finitely parameterized family of approximate value functions, and introduce a variant of value iteration, adapted to this parametric setting. We also introduce a related method which uses a single (parameterized) value function, which is a function of the time-state pair, as opposed to using a separate (independently parameterized) value function for each time. Our methods involve the evaluation of value functions at a finite set, consisting of "representative" elements of the state space. We show that with an arbitrary choice of this set, the approximation error can grow exponentially with the time horizon (time to expiration). On the other hand, if representative states are chosen by simulating the state process using the underlying risk-neutral probability distribution, then the approximation error remains bounded.
A Tractable POMDP for a Class of Sequencing Problems

We consider a partially observable Markov decision problem (POMDP) that models a class of sequencing problems. Although POMDPs are typically intractable, our formulation admits tractable solution. Instead of maintaining a value function over a highdimensional set of belief states, we reduce the state space to one of smaller dimension, in which grid-based dynamic programming techniques are effective. We develop an error bound for the resulting approximation, and discuss an application of the model to a problem in targeted advertising.
An analysis of belief propagation on the turbo decoding graph with Gaussian densities

Motivated by its success in decoding turbo codes, we provide an analysis of the belief propagation algorithm on the turbo decoding graph with Gaussian densities. In this context, we are able to show that, under certain conditions, the algorithm converges and that-somewhat surprisingly-though the density generated by belief propagation may differ significantly from the desired posterior density, the means of these two densities coincide. Since computation of posterior distributions is tractable when densities are Gaussian, use of belief propagation in such a setting may appear unwarranted. Indeed, our primary motivation for studying belief propagation in this context stems from a desire to enhance our understanding of the algorithm's dynamics in a non-Gaussian setting, and to gain insights into its excellent performance in turbo codes. Nevertheless, even when the densities are Gaussian, belief propagation may sometimes provide a more efficient alternative to traditional inference methods.
InP-based waveguides: comparison of ECR plasma etching and wet-chemical etching

1 COBRA Inter-University Research Institute on Communication Technology Eindhoven University of Technology –Faculty of Electrical Engineering Telecommunications Technology and Electromagnetics – Opto-Electronic Devices Group P.O.Box 513, 5600 MB Eindhoven, The Netherlands E-mail: j.j.g.m.v.d.tol@tue.nl 2 Department of Electronic Materials Engineering, Research School of Physical Sciences and Engineering, Australian National University, Canberra, ACT 0200,
The optimal harvesting of environmental bads

Our analysis molds two traditional approaches to promoting quality. The first is restoring the stock of quality. The second is curbing its flow of deterioration. Although both approaches are widely used in real world settings, analytic models have tended to focus on one strategy or the other. We consider a class of problems, which we call "SFQ" problems, in which both stocks and flows can be controlled to promote quality. We develop our results in the context of environmental quality, drawing on real-world examples from atomic wastes to zebra mussels. But the lessons are general, and we show how they apply to promoting the quality of both physical and human capital.
Optimal stopping of Markov processes: Hilbert space theory, approximation algorithms, and an application to pricing high-dimensional financial derivatives

The authors develop a theory characterizing optimal stopping times for discrete-time ergodic Markov processes with discounted rewards. The theory differs from prior work by its view of per-stage and terminal reward functions as elements of a certain Hilbert space. In addition to a streamlined analysis establishing existence and uniqueness of a solution to Bellman's equation, this approach provides an elegant framework for the study of approximate solutions. In particular, the authors propose a stochastic approximation algorithm that tunes weights of a linear combination of basis functions in order to approximate a value function. They prove that this algorithm converges (almost surely) and that the limit of convergence has some desirable properties. The utility of the approximation method is illustrated via a computational case study involving the pricing of a path dependent financial derivative security that gives rise to an optimal stopping problem with a 100-dimensional state space.
Sealing method of dry etched AlAs/GaAs top mirrors in vertical cavity surface emitting lasers

A versatile sealing process for AlAs layers is presented. This sealing prevents the AlAs layers of AlAs/GaAs top distributed Bragg reflectors from further undesired oxidation during the wet oxidation of the AlAs current constriction layers in vertical cavity surface emitting lasers. This method has been successfully applied to protect the etched pillars in top mirrors although those pillars were plasma dry etched.  S1099-0062(98)07-019-9. All rights reserved.
Learning and value function approximation in complex decision processes

In principle, a wide variety of sequential decision problems--ranging from dynamic resource allocation in telecommunication networks to financial risk management--can be formulated in terms of stochastic control and solved by the algorithms of dynamic programming. Such algorithms compute and store a value function, which evaluates expected future reward as a function of current state. Unfortunately, exact computation of the value function typically requires time and storage that grow proportionately with the number of states, and consequently, the enormous state spaces that arise in practical applications render the algorithms intractable. 
In this thesis, we study tractable methods that approximate the value function. Our work builds on research in an area of artificial intelligence known as reinforcement learning. A point of focus of this thesis is temporal-difference learning--a stochastic algorithm inspired to some extent by phenomena observed in animal behavior. Given a selection of basis functions, the algorithm updates weights during simulation of the system such that the weighted combination of basis functions ultimately approximates a value function. We provide an analysis (a proof of convergence, together with bounds on approximation error) of temporal-difference learning in the context of autonomous (uncontrolled) systems as applied to the approximation of (1) infinite horizon discounted rewards and (2) average and differential rewards. 
As a special case of temporal-difference learning in a context involving control, we propose variants of the algorithm that generate approximate solutions to optimal stopping problems. We analyze algorithms designed for several problem classes: (1) optimal stopping of a stationary mixing process with an infinite horizon and discounted rewards; (2) optimal stopping of an independent increments process with an infinite horizon and discounted rewards; (3) optimal stopping with a finite horizon and discounted rewards; (4) a zero-sum two-player stopping game with an infinite horizon and discounted rewards. We also present a computational case study involving a complex optimal stopping problem that is representative of those arising in the financial derivatives industry. 
In addition to algorithms for tuning basis function weights, we study an approach to basis function generation. In particular, we explore the use of "scenarios" that are representative of the range of possible events in a system. Each scenario is used to construct a basis function that maps states to future rewards contingent on the future realization of the scenario. We derive, in the context of autonomous systems, a bound on the number of "representative scenarios" that suffices for uniformly accurate approximation of the value function. The bound exhibits a dependence on a measure of "complexity" of the system that can often grow at a rate much slower that the state space size. (Copies available exclusively from MIT Libraries Rm. 14-0551, Cambridge, MA 02139-4307 Ph. 617-253-5668; Fax 617-253-1690.
Analysis of Temporal-Diffference Learning with Function Approximation

We present new results about the temporal-difference learning algorithm, as applied to approximating the cost-to-go function of a Markov chain using linear function approximators. The algorithm we analyze performs on-line updating of a parameter vector during a single endless trajectory of an aperiodic irreducible finite state Markov chain. Results include convergence (with probability 1), a characterization of the limit of convergence, and a bound on the resulting approximation error. In addition to establishing new and stronger results than those previously available, our analysis is based on a new line of reasoning that provides new intuition about the dynamics of temporal-difference learning. Furthermore, we discuss the implications of two counter-examples with regards to the Significance of on-line updating and linearly parameterized function approximators.
Approximate Solutions to Optimal Stopping Problems

We propose and analyze an algorithm that approximates solutions to the problem of optimal stopping in a discounted irreducible aperiodic Markov chain. The scheme involves the use of linear combinations of fixed basis functions to approximate a Q-function. The weights of the linear combination are incrementally updated through an iterative process similar to Q-learning, involving simulation of the underlying Markov chain. Due to space limitations, we only provide an overview of a proof of convergence (with probability 1) and bounds on the approximation error. This is the first theoretical result that establishes the soundness of a Q-learning-like algorithm when combined with arbitrary linear function approximators to solve a sequential decision problem. Though this paper focuses on the case of finite state spaces, the results extend naturally to continuous and unbounded state spaces, which are addressed in a forthcoming full-length paper.
Stable LInear Approximations to Dynamic Programming for Stochastic Control Problems with Local Transitions

We consider the solution to large stochastic control problems by means of methods that rely on compact representations and a variant of the value iteration algorithm to compute approximate cost-togo functions. While such methods are known to be unstable in general, we identify a new class of problems for which convergence, as well as graceful error bounds, are guaranteed. This class involves linear parameterizations of the cost-to-go function together with an assumption that the dynamic programming operator is a contraction with respect to the Euclidean norm when applied to functions in the parameterized class. We provide a special case where this assumption is satisfied, which relies on the locality of transitions in a state space. Other cases will be discussed in a full length version of this paper.
Adaptive Video Fast Forward

We derive a statistical graphical model of video scenes with multiple, possibly occluded objects that can be efficiently used for tasks related to video search, browsing and retrieval. The model is trained on query (target) clip selected by the user. Shot retrieval process is based on the likelihood of a video frame under generative model. Instead of using a combination of weighted Euclidean distances as a shot similarity measure, the likelihood model automatically separates and balances various causes of variability in video, including occlusion, appearance change and motion. Thus, we overcome tedious and complex user interventions required in previous studies. We use the model in the adaptive video forward application that adapts video playback speed to the likelihood of the data. The similarity measure of each candidate clip to the target clip defines the playback speed. Given a query, the video is played at a higher speed as long as video content has low likelihood, and when frames similar to the query clip start to come in, the video playback rate drops. Set of experiments o12n typical home videos demonstrate performance, easiness and utility of our application.
Epitomic Analysis of Human Motion

Epitomic analysis is a recent statistical approach to form a generative model. It has been recently applied to image, video, and audio data. In this paper, we describe a novel application of epitomic analysis to motion capture data. We show how to construct a motion epitome, and use it for various applications in animation such as motion synthesis, reconstruction and classification of motions. We discuss the use of motion epitome for measuring motion naturalness.
Interactive Montages of Sprites for Indexing and Summarizing Security Video

In this video we present a new model of interaction for indexing and visualizing video in the context of security applications. We present a method of indexing video by arranging irregularly shaped icons or sprites into a montage representing motion events or security events within the original video scene. The sprites in the montage are used as an index into the original video. We also generate video montages to summarize video in which motion events are compressed and overlayed in a video of shorter time duration. This summary video also acts as an index into the original video stream. We use a simple, novel method of extracting sprites for the image and video montages based on incrementally building a Gaussian mixture model with conjugate priors for the background. We then use fast morphological operators to extract foreground elements. Our approach can be viewed as a fast maximum a posteriori (MAP) inference procedure in a layered image model. The contributions of this work are new interaction and summary schemes that allow viewers to potentially survey hours of security video in the order of minutes.