Search

We consider optimization problems whose parameters are known only approximately, based on noisy samples. In large-scale applications, the number of samples one can collect is typically of the same order [...]

Robust optimization is a common optimization framework under uncertainty when problem parameters are unknown, but it is known that they belong to some given uncertainty set. In the robust optimization [...]

Solving the Hamilton-Jacobi-Bellman equation is important in many domains including control, robotics and economics. Especially for continuous control, solving this differential equation and its extension the Hamilton-Jacobi-Isaacs equation, is important as it yields the optimal policy that achieves the maximum reward on a give task. In the case of the Hamilton-Jacobi-Isaacs equation, which includes an adversary controlling the environment and minimizing the reward, the obtained policy is also robust to perturbations of the dynamics. In this paper we propose continuous fitted value iteration (cFVI) and robust fitted value iteration (rFVI). These algorithms leverage the non-linear control-affine dynamics and separable state and action reward of many continuous control problems to derive the optimal policy and optimal adversary in closed form. This analytic expression simplifies the differential equations and enables us to solve for the optimal value function using value iteration for continuous actions and states as well as the adversarial case. Notably, the resulting algorithms do not require discretization of states or actions. We apply the resulting algorithms to the Furuta pendulum and cartpole. We show that both algorithms obtain the optimal policy. The robustness Sim2Real experiments on the physical systems show that the policies successfully achieve the task in the real-world. When changing the masses of the pendulum, we observe that robust value iteration is more robust compared to deep reinforcement learning algorithm and the non-robust version of the algorithm. Videos of the experiments are shown at https://sites.google.com/view/rfvi.

Chance constraints are an important modeling tool in stochastic optimization, providing probabilistic guarantees that a solution 'succeeds' in satisfying a given constraint. Although they control the probability of 'success,' they [...]

Markov decision processes are an effective tool in modeling decision making in uncertain dynamic environments. Because the parameters of these models typically are estimated from data or learned from experience, [...]

AAAI presented the AAAI-04 workshop program on Sunday July 25 and Monday, July 26, 2004 at the San Jose McEnery Convention Center and the adjacent headquarter hotel in San Jose, […], AAAI presented the AAAI-04 workshop program on July 25-26, 2004 in San Jose, California. This program included twelve workshops covering a wide range of topics in artificial intelligence. The titles of the workshops were as follows: (1) Adaptive Text Extraction and Mining; (2) Agent Organizations: Theory and Practice; (3) Anchoring Symbols to Sensor Data; (4) Challenges in Game AI; (5) Fielding Applications of Artificial Intelligence; (6) Forming and Maintaining Coalitions in Adaptive Multiagent Systems; (7) Intelligent Agent Architectures: Combining the Strengths of Software Engineering and Cognitive Systems; (8) Learning and Planning in Markov Processes--Advances and Challenges; (9) Semantic Web Personalization; (10) Sensor Networks; (11) Spatial and Temporal Reasoning; and (12) Supervisory Control of Learning and Adaptive Systems.

Ultrashort laser pulses with femtosecond to attosecond pulse duration are the shortest systematic events humans can currently create. Characterization (amplitude and phase) of these pulses is a crucial ingredient in ultrafast science, e.g., exploring chemical reactions and electronic phase transitions. Here, we propose and demonstrate, numerically and experimentally, what is to the best of our knowledge, the first deep neural network technique to reconstruct ultrashort optical pulses. Employing deep neural networks for reconstruction of ultrashort pulses enables diagnostics of very weak pulses and offers new possibilities, e.g., reconstruction of pulses using measurement devices without knowing in advance the relations between the pulses and the measured signals. Finally, we demonstrate the ability to reconstruct ultrashort pulses from their experimentally measured frequency-resolved optical gating traces via deep networks that have been trained on simulated data.

We provide sampling-based algorithms for optimization under a coherent-risk objective. The class of coherent-risk measures is widely accepted in finance and operations research, among other fields, and encompasses popular risk-measures such as conditional value at risk and mean-semi-deviation. Our approach is suitable for problems in which tuneable parameters control the distribution of the cost, such as in reinforcement learning or approximate dynamic programming with a parameterized policy. Such problems cannot be solved using previous approaches. We consider both static risk measures and time-consistent dynamic risk measures. For static risk measures, our approach is in the spirit of policy gradient methods, while for the dynamic risk measures, we use actor-critic type algorithms. [ABSTRACT FROM PUBLISHER]

Advanced machine learning (ML) algorithms have outperformed traditional approaches in various forecasting applications, especially electricity price forecasting (EPF). However, the prediction accuracy of ML reduces substantially if the input data is not similar to the ones seen by the model during training. This is often observed in EPF problems when market dynamics change owing to a rise in fuel prices, an increase in renewable penetration, a change in operational policies, etc. While the dip in model accuracy for unseen data is a cause for concern, what is more, challenging is not knowing when the ML model would respond in such a manner. Such uncertainty makes the power market participants, like bidding agents and retailers, vulnerable to substantial financial loss caused by the prediction errors of EPF models. Therefore, it becomes essential to identify whether or not the model prediction at a given instance is trustworthy. In this light, this paper proposes a trust algorithm for EPF users based on explainable artificial intelligence techniques. The suggested algorithm generates trust scores that reflect the model’s prediction quality for each new input. These scores are formulated in two stages: in the first stage, the coarse version of the score is formed using correlations of local and global explanations, and in the second stage, the score is fine-tuned further by the Shapley additive explanations values of different features. Such score-based explanations are more straightforward than feature-based visual explanations for EPF users like asset managers and traders. A dataset from Italy’s and ERCOT’s electricity market validates the efficacy of the proposed algorithm. Results show that the algorithm has more than 85% accuracy in identifying good predictions when the data distribution is similar to the training dataset. In the case of distribution shift, the algorithm shows the same accuracy level in identifying bad predictions.

We consider the dynamics of rapid propagation of information (RPI) in mobile phone networks. We propose a heuristic method for identification of sequences of calls that supposedly propagate the same information and apply it to large-scale real-world data. We show that some of the information propagation events identified by the proposed method can explain the physical co-location of subscribers. We further show that features of subscriber’s behavior in these events can be used for efficient churn prediction. To the best of our knowledge, our method for churn prediction is the first method that relies on dynamic, rather than static, social behavior. Finally, we introduce two generative models that address different aspects of RPI. One model describes the emergence of sequences of calls that lead to RPI. The other model describes the emergence of different topologies of paths in which the information propagates from one subscriber to another. We report high correspondence between certain features observed in the data and these models.

We consider scheduling over a wireless system in which the channel state information is not available a priori to the scheduler but can be inferred from past history. Specifically, the wireless system is modeled as a network of parallel queues. We assume that the channel state of each queue evolves stochastically as an independent on/offMarkov chain. The scheduler, which is aware of the queue lengths but is ignorant of the channel states, has to choose at most one queue at a time for transmission. The scheduler has no information regarding the current channel states but can estimate them from the acknowledgment history. We first characterize the capacity region of the system using tools from the theory of Markov decision processes (MDPs). Specifically, we prove that the capacity region boundary is the uniform limit of a sequence of linear programming (LP) solutions. Next, we combine the LP solution with a queue-length-based scheduling mechanism that operates over long frames to obtain a throughput optimal policy for the system. By incorporating results from MDP theory within the Lyapunov-stability framework, we show that our frame-based policy stabilizes the system for all arrival rates that lie in the interior of the capacity region.

Computer (and human) networks have long had to contend with spreading viruses. Effectively controlling or curbing an outbreak requires understanding the dynamics of the spread. A virus that spreads by taking advantage of physical links or user-acquaintance links on a social network can grow explosively if it spreads beyond a critical radius. On the other hand, random infections (that do not take advantage of network structure) have very different propagation characteristics. If too many machines (or humans) are infected, network structure becomes essentially irrelevant, and the different spreading modes appear identical. When can we distinguish between mechanics of infection? Further, how can this be done efficiently? This paper studies these two questions. We provide sufficient conditions for different graph topologies, for when it is possible to distinguish between a random model of infection and a spreading epidemic model, with probability of misclassification going to zero. We further provide efficient algorithms that are guaranteed to work in different regimes.

We consider a network formation game where nodes wish to send traffic to each other. Nodes contract bilaterally with each other to form bidirectional communication links; once the network is formed, traffic is routed along shortest paths (if possible). Cost is incurred to a node from four sources: 1) routing traffic; 2) maintaining links to other nodes; 3) disconnection from destinations the node wishes to reach; and 4) payments made to other nodes. We assume that a network is stable if no single node wishes to unilaterally deviate, and no pair of nodes can profitably deviate together (a variation on the notion of pairwise stability). We study such a game under a form of myopic best response dynamics. In choosing their action, nodes optimize their single period payoff only. We characterize a simple set of assumptions under which these dynamics converge to a stable network; we also characterize an important special case, where the dynamics converge to a star centered at a node with minimum cost for routing traffic. In this sense, our dynamics naturally select an efficient equilibrium. [ABSTRACT FROM AUTHOR]

We consider filter design of a linear system with parameter uncertainty. In contrast to the robust Kalman filter which focuses on a worst case analysis, we propose a design methodology based on iteratively solving a tradeoff problem between nominal performance and robustness to the uncertainty. Our proposed filter can be computed online efficiently, is steady-state stable, and is less conservative than the robust filter. [ABSTRACT FROM AUTHOR]

This note presents a new design methodology that allows for flexible management of the tradeoff between the ability of a system to attenuate disturbance signals versus its expected worst peak-to-peak amplification. The proposed strategy applies to linear time-invariant systems which are subject to persistent disturbance signals and combines a recently developed quasi-robust linear programming concept with a well-known l1-optimal controller synthesis approach. The benefit of the resulting technique is demonstrated using an example. [ABSTRACT FROM AUTHOR]

We consider a resource allocation problem where individual users wish to send data across a network to maximize their utility, and a cost is incurred at each link that depends on the total rate sent through the link. It is known that as long as users do not anticipate the effect of their actions on prices, a simple proportional pricing mechanism can maximize the sum of users' utilities minus the cost (called aggregate surplus). Continuing previous efforts to quantify the effects of selfish behavior in network pricing mechanisms, we consider the possibility that users anticipate the effect of their actions on link prices. Under the assumption that the links' marginal cost functions are convex, we establish existence of a Nash equilibrium. We show that the aggregate surplus at a Nash equilibrium is no worse than a factor of 4√2-5 times the optimal aggregate surplus; thus, the efficiency loss when users are selfish is no more than approximately 34%. [ABSTRACT FROM AUTHOR]

We consider the existence of a linear weak learner for boosting algorithms. A weak learner for binary classification problems is required to achieve a weighted empirical error on the training set which is bounded from above by 1/2 − γ, γ > 0, for any distribution on the data set. Moreover, in order that the weak learner be useful in terms of generalization, γ must be sufficiently far from zero. While the existence of weak learners is essential to the success of boosting algorithms, a proof of their existence based on a geometric point of view has been hitherto lacking. In this work we show that under certain natural conditions on the data set, a linear classifier is indeed a weak learner. Our results can be directly applied to generalization error bounds for boosting, leading to closed-form bounds. We also provide a procedure for dynamically determining the number of boosting iterations required to achieve low generalization error. The bounds established in this work are based on the theory of geometric discrepancy.