nils-herrmann/clean_scirepeval huggingface dataset:
Learning with attribute costs

We study an extension of the "standard" learning models to settings where observing the value of an attribute has an associated cost (which might be different for different attributes). Our model assumes that the correct classification is given by some target function f from a class of functions cal F; most of our results discuss the ability to learn a clause (an OR function of a subset of the variables) in various settings: We are given both the function f and the distribution D that is used to generate an input x. The goal is to design a strategy to decide what attribute of x to observe next so as to minimize the expected evaluation cost of f(x). (In this setting there is no "learning" to be done but only an optimization problem to be solved; this problem to be NP-hard and hence approximation algorithms are presented.)Distributional online: We study two types of "learning" problems; one where the target function f is known to the learner but the distribution D is unknown (and the goal is to minimize the expected cost including the cost that stems from "learning" D), and the other where f is unknown (except that f∈cal F) but D is known (and the goal is to minimize the expected cost while limiting the prediction error involved in "learning" f).Adversarial online: We are given f, however the inputs are selected adversarially. The goal is to compare the learner's cost to that of the best fixed evaluation order (i.e., we analyze the learner's performance by a competitive analysis).
On Regret and Options-A Game Theoretic Approach for Option Pricing †

We study the link between the game theoretic notion of ’regret minimization’ and robust option pricing. We demonstrate how trading strategies that minimize regret also imply robust upper bounds for the prices of European call options. These bounds are based on ’no-arbitrage’ and are robust in that they require only minimal assumptions regarding the stock price process. We then focus on the optimal bounds and demonstrate that they can be expressed as a value of a zero sum game. We solve for the optimal volatility-based bounds in closed-form, which in turn implies the optimal regret minimizing trading strategy. † We thank Sergiu Hart for helpful discussion and seminar participants at Berkeley (IEOR), Tel Aviv university, Hebrew University and Stanford for useful comments.
Fast convergence of selfish rerouting

We consider n anonymous selfish users that route their communication through m parallel links. The users are allowed to reroute, concurrently, from overloaded links to underloaded links. The different rerouting decisions are concurrent, randomized and independent. The rerouting process terminates when the system reaches a Nash equilibrium, in which no user can improve its state.We study the convergence rate of several migration policies. The first is a very natural policy, which balances the expected load on the links, for the case that all users are identical and apply it, we show that the rerouting terminates in expected O(log log n + log m) stages. Later, we consider the Nash rerouting policies class, in which every rerouting stage is a Nash equilibrium and the users are greedy with respect to the next load they observe. We show a similar termination bounds for this class. We study the structural properties of the Nash rerouting policies, and derive both existence result and an efficient algorithm for the case that the number of links is small. We also show that if the users have different weights then there exists a set of weights such that every Nash rerouting terminates in Ω(√n) stages with high probability.
Optimizing TCP Retransmission Timeout

Delay spikes on Internet paths can cause spurious TCP timeouts leading to significant throughput degradation. However, if TCP is too slow to detect that a retransmission is necessary, it can stay idle for a long time instead of transmitting. The goal is to find a Retransmission Timeout (RTO) value that balances the throughput degradation between both of these cases. In the current TCP implementations, RTO is a function of the Round Trip Time (RTT) alone. We show that the optimal RTO that maximizes the TCP throughput need to depend also on the TCP window size. Intuitively, the larger the TCP window size, the longer the optimal RTO. We derive the optimal RTO for several RTT distributions. An important advantage of our algorithm is that it can be easily implemented based on the existing TCP timeout mechanism.
Concentration Bounds for Unigram Language Models

Natural language processing (NLP) has developed rapidly over the las t decades. It has a wide range of applications, including speech recognition, optical character recogn iti n, text categorization and many more. The theoretical analysis has also advanced significantly, thoug h many fundamental questions remain unanswered. One clear challenge, both practical and th eoretical, concerns deriving stochastic models for natural languages. Consider a simple language model, where the distribution of each word in the tex t is assumed to be independent. Even for such a simplistic model, fundamental questions rela ting s mple size to the learning accuracy are already challenging. This is mainly due to the fact that the sample size is almost always insufficient, regardless of how large it is. To demonstrate this phenomena, consider the following example. We would like to estimate the distribution of first names in the university. For that, we are given the na mes list of a graduate seminar: Alice, Bob, Charlie, Dan, Eve, Frank, two Georges, and two He nries. How can we use this sample to estimate the distribution of students’ first names? An empirical frequen cy estimator would
Concentration Bounds for Unigrams Language Model

We show several high-probability concentration bounds for learning unigram language models. One interesting quantity is the probability of all words appearing exactly k times in a sample of size m. A standard estimator for this quantity is the Good-Turing estimator. The existing analysis on its error shows a high-probability bound of approximately O(k / m1/2). We improve its dependency on k to O(k1/4 / m1/2 + k / m). We also analyze the empirical frequencies estimator, showing that with high probability its error is bounded by approximately O( 1 / k + k1/2 / m). We derive a combined estimator, which has an error of approximately O(m-2/5), for any k.A standard measure for the quality of a learning algorithm is its expected per-word log-loss. The leave-one-out method can be used for estimating the log-loss of the unigram model. We show that its error has a high-probability bound of approximately O(1 / m1/2), for any underlying distribution.We also bound the log-loss a priori, as a function of various parameters of the distribution.
An Experimental and Theoretical Comparison of Model Selection Methods

We investigate the problem of model selection in the setting of supervised learning of boolean functions from independent random examples. More precisely, we compare methods for finding a balance between the complexity of the hypothesis chosen and its observed error on a random training sample of limited size, when the goal is that of minimizing the resulting generalization error. We undertake a detailed comparison of three well-known model selection methods — a variation of Vapnik's Guaranteed Risk Minimization (GRM), an instance of Rissanen's Minimum Description Length Principle (MDL), and (hold-out) cross validation (CV). We introduce a general class of model selection methods (called penalty-based methods) that includes both GRM and MDL, and provide general methods for analyzing such rules. We provide both controlled experimental evidence and formal theorems to support the following conclusions:•Even on simple model selection problems, the behavior of the methods examined can be both complex and incomparable. Furthermore, no amount of “tuning” of the rules investigated (such as introducing constant multipliers on the complexity penalty terms, or a distribution-specific “effective dimension”) can eliminate this incomparability.•It is possible to give rather general bounds on the generalization error, as a function of sample size, for penalty-based methods. The quality of such bounds depends in a precise way on the extent to which the method considered automatically limits the complexity of the hypothesis selected.•For any model selection problem, the additional error of cross validation compared to any other method can be bounded above by the sum of two terms. The first term is large only if the learning curve of the underlying function classes experiences a phase transition” between (1-γ)m and m examples (where gamma is the fraction saved for testing in CV). The second and competing term can be made arbitrarily small by increasing γ.•The class of penalty-based methods is fundamentally handicapped in the sense that there exist two types of model selection problems for which every penalty-based method must incur large generalization error on at least one, while CV enjoys small generalization error on both.
Experts in a Markov Decision Process

We consider an MDP setting in which the reward function is allowed to change during each time step of play (possibly in an adversarial manner), yet the dynamics remain fixed. Similar to the experts setting, we address the question of how well can an agent do when compared to the reward achieved under the best stationary policy over time. We provide efficient algorithms, which have regret bounds with no dependence on the size of state space. Instead, these bounds depend only on a certain horizon time of the process and logarithmically on the number of actions. We also show that in the case that the dynamics change over time, the problem becomes computationally hard.
Buffer Overflow Management in QoS Switches

We consider two types of buffering policies that are used in network switches supporting Quality of Service (QoS). In the FIFO type, packets must be transmitted in the order in which they arrive; the constraint in this case is the limited buffer space. In the bounded-delay type, each packet has a maximum delay time by which it must be transmitted, or otherwise it is lost. We study the case of overloads resulting in packet loss. In our model, each packet has an intrinsic value, and the goal is to maximize the total value of transmitted packets. 
Our main contribution is a thorough investigation of some natural greedy algorithms in various models. For the FIFO model we prove tight bounds on the competitive ratio of the greedy algorithm that discards packets with the lowest value when an overflow occurs. We also prove that the greedy algorithm that drops the earliest packets among all low-value packets is the best greedy algorithm. This algorithm can be as much as 1.5 times better than the tail-drop greedy policy, which drops the latest lowest-value packets. 
In the bounded-delay model we show that the competitive ratio of any on-line algorithm for a uniform bounded-delay buffer is bounded away from 1, independent of the delay size. We analyze the greedy algorithm in the general case and in three special cases: delay bound 2, link bandwidth 1, and only two possible packet values. 
Finally, we consider the off-line scenario. We give efficient optimal algorithms and study the relation between the bounded-delay and FIFO models in this case.
8.1 Regret 8.2 Basic Model 8.3 a Greedy Algorithm

Assuming that the opponent has the same stochastic strategy at each step, how should we play? Let’s formalize this: • N actions • For each step t, we choose a distribution p over the N actions • For each step, we have a loss l where l(i) ∈ [0, 1] is the loss from action i • Our loss is Ni=1 p(i)l(i) Note that we do not rely on the number of opponents or on their actions. Once we assume that the opponent is constant and does not depend on us, then the opponent’s influence is only on the cost of each action. Our goals: • Bring the loss to a minimum • Choose the best action (the opponent does not change throughout time)
A Sparse Sampling Algorithm for Near-Optimal Planning in Large Markov Decision Processes

A critical issue for the application of Markov decision processes (MDPs) to realistic problems is how the complexity of planning scales with the size of the MDP. In stochastic environments with very large or infinite state spaces, traditional planning and reinforcement learning algorithms may be inapplicable, since their running time typically grows linearly with the state space size in the worst case. In this paper we present a new algorithm that, given only a generative model (a natural and common type of simulator) for an arbitrary MDP, performs on-line, near-optimal planning with a per-state running time that has no dependence on the number of states. The running time is exponential in the horizon time (which depends only on the discount factor γ and the desired degree of approximation to the optimal policy). Our algorithm thus provides a different complexity trade-off than classical algorithms such as value iteration—rather than scaling linearly in both horizon time and state space size, our running time trades an exponential dependence on the former in exchange for no dependence on the latter.Our algorithm is based on the idea of sparse sampling. We prove that a randomly sampled look-ahead tree that covers only a vanishing fraction of the full look-ahead tree nevertheless suffices to compute near-optimal actions from any state of an MDP. Practical implementations of the algorithm are discussed, and we draw ties to our related recent results on finding a near-best strategy from a given class of strategies in very large partially observable MDPs (Kearns, Mansour, & Ng. Neural information processing systems 13, to appear).
Implementation Issues in the Fourier Transform Algorithm

The Fourier transform of Boolean functions has received considerable attention in the last few years in the computational learning theory community, and has come to play an important role in proving many important learnability results. The aim of this work is to demonstrate that the Fourier transform techniques are also a useful and practical algorithm, in addition to having many interesting theoretical properties. In fact, this work was prompted by a genuine problem that was brought to our attention; researchers at a company were trying to come by a method to reverse-engineer a state-free controller. They had the capability of querying the controller on any input, thus setting them in the membership query model, in which the Fourier transform algorithm is set.In order to keep the algorithm run-time reasonable and still produce accurate hypotheses, we had to perform many optimizations. In the paper we discuss the more prominent optimizations, ones that were crucial and without which the performance of the algorithm would severely deteriorate. One of the benefits we present is the confidence level the algorithm produces in addition to the predictions. The confidence level measures the likelihood that the prediction is correct.
5.1 Introduction 5.2 Proof of Existence of Stochastic Nash Equilib- Rium in Any Game 5.2.1 Proof Outline

In this lecture we explore issues concerning the computability of Nash Equilibrium in any general game. First we prove any game has at least one Nash Equilibrium using Brouwer’s Fixed Point Theorem (The proof is presented at section 5.6 ). Then we discuss how to compute a Nash Equilibrium of a game and a Nash Equilibrium approximation called -Nash. We conclude by proving that the computation of most information concerning Nash Equilibrium is NP -hard.
Competitive on-line paging strategies for mobile users under delay constraints

A mobile user is roaming in a zone of n cells in a cellular network system. When a call for the mobile arrives, the system pages the mobile in these cells since it never reports its location unless it leaves the zone. A delay constraint paging strategy must find the mobile after at most 1 ≤ D ≤ n paging rounds each pages a subset of the n cells. The goal is to minimize the number of paged cells until the mobile is found. Optimal solutions are known for the off-line case, for which an a priori probability of a mobile residing in any one of the cells is known. In this paper we address the on-line case. An on-line paging strategy makes its decisions based only on past locations of the mobile while trying to learn its future locations.We present deterministic and randomized on-line algorithms for various values of D (number of paging rounds) as a function of n (number of cells) and evaluate them using competitive analysis. In particular, we present a constant competitive on-line algorithm for the two extreme cases of D=2 and D=n. The former is the first nontrivial delay constraint case and the latter is the case for which there are no delay constraints. We then show that the constant competitiveness can be attained already for D ≥ log2n. All of the above algorithms are deterministic. Our randomized on-line algorithm achieves a near optimal performance for all values of D. This algorithm is based on solutions to the best expert problem.
Improved combination of online algorithms for acceptance and rejection

Given two admission control algorithms that are <i>c<inf>A</inf></i>-accept-competitive and <i>c<inf>R</inf></i>-reject-competitive respectively, we give two ways to make an algorithm that is simultaneously <i>O</i>(<i>c<inf>A</inf></i>)-accept-competitive and <i>O</i>(<i>c<inf>A</inf></i><i>c<inf>R</inf></i>)-reject-competitive. The combined algorithms make no reference to the offline optimal solution. In addition, one of the algorithms does not require knowing the value of either <i>c<inf>A</inf></i> or <i>c<inf>R</inf></i>. This improves on work of Azar, Blum, and Mansour, whose combined algorithm was <i>O</i>(<i>c<sup>2</sup><inf>A</inf></i>)-accept-competitive, involved computing offline optimal solutions, and required knowing the values of both <i>c<inf>A</inf></i> and <i>c<inf>R</inf></i>.
2.1 Coordination Ratio

Assume there is a network of parallel lines from an origin to a destination as shown in figure 2.1. Several agents want to send a particular amount of traffic along a path from the source to the destination. The more traffic on a particular line, the longer the traffic delay. • Allocation jobs to machines as shown in figure 2.2. Each job has a different size and each machine has a different speed. The performance of each machine reduces as more jobs are allocated to it. An example for a global optimum function, in this case, would be to minimize the load on the most loaded machine.
1 Extensive Games with Perfect Information

7.1.1 Definitions Definition An extensive game with perfect information 〈N, H, P, Ui〉 has the following components: • A set of N players • A set H of sequences (finite or infinite). each member of H is a history; each component of a history ia an action taken by a player. • P is the player function, P (h) being the player who takes an action after the history h. • Payoff function Ui, i ∈ N After any history h player P (h) chooses an action from the set A(h) = {a : (h, a) ∈ H}. The empty history is the starting point of the game.
Auctions with Budget Constraints

In a combinatorial auction k different items are sold to n bidders, where the objective of the seller is to maximize the revenue. The main difficulty to find an optimal allocation is due to the fact that the valuation function of each bidder for bundles of items is not necessarily an additive function over the items. An auction with budget constraints is a common special case where bidders generally have additive valuations, yet they have a limit on their maximal valuation. Auctions with budget constraints were analyzed by Lehmann, Lehmann and Nisan [11], as part of a wider class of auctions, where they have shown that maximizing the revenue is NP-hard, and presented a greedy 2-approximation algorithm. In this paper we present exact and approximate algorithms for auctions with budget constraints. We present a randomized algorithm with an approximation ratio of \(\frac{e}{e-1}\cong\) 1.582, which can be derandomized. We analyze the special case where all bidders have the same budget constraint, and show an algorithm whose approximation ratio is between 1.3837 and 1.3951. We also present an FPTAS for the case of a constant number of bidders.
Competitive Management of Non-preemptive Queues with Multiple Values

We consider the online problem of active queue management. In our model, the input is a sequence of packets with values v ∈ [1,α] that arrive to a queue that can hold up to B packets. Specifically, we consider a FIFO non-preemptive queue, where any packet that is accepted into the queue must be sent, and packets are sent by the order of arrival. The benefit of a scheduling policy, on a given input, is the sum of values of the scheduled packets. Our aim is to find an online policy that maximizes its benefit compared to the optimal offline solution.
Improved Competitive Guarantees for QoS Buffering

We consider a network providing Differentiated Services (Diffserv) which allow Internet service providers (ISP) to offer different levels of Quality of Service (QoS) to different traffic streams. We study FIFO buffering algorithms, where packets must be transmitted in the order they arrive. The buffer space is limited, and packets are lost if the buffer is full. Each packet has an intrinsic value, and the goal is to maximize the total value of transmitted packets. Our main contribution is an algorithm for arbitrary packet values that for the first time achieves a competitive ratio better than 2, namely 2-e for a constant e> 0.
Approximate Equivalence of Markov Decision Processes

We consider the problem of finding the minimal e-equivalent MDP for an MDP given in its tabular form. We show that the problem is NP-Hard and then give a bicriteria approximation algorithm to the problem. We suggest that the right measure for finding minimal e-equivalent model is L 1 rather than L ∞ by giving both an example, which demonstrates the drawback of using L ∞ , and performance guarantees for using L 1. In addition, we give a polynomial algorithm that decides whether two MDPs are equivalent.
Competitive queueing policies for QoS switches

We consider packet scheduling in a network providing differentiated services, where each packet is assigned a value. We study various queueing models for supporting QoS (Quality of Service). In the nonpreemptive model, packets accepted to the queue will be transmitted eventually and cannot be dropped. The FIFO preemptive model allows packets accepted to the queue to be preempted (dropped) prior to their departure, while ensuring that transmitted packets are sent in the order of arrival. In the bounded delay model, packets must be transmitted before a certain deadline, otherwise it is lost (while transmission ordering is allowed to be arbitrary). In all models the goal of the buffer policy is to maximize the total value of the accepted packets.Let α be the ratio between the maximal and minimal value. For the non-preemptive model we derive a Θ(log &alpha) competitive ratio, both exhibiting a buffer policy and a general lower bound. For the interesting case of two distinct values, we give an 2α--1/α competitive buffer policy, which exactly matches the lower bound. We also analyze a RED-like policy and derive its competitive ratio, which is approximately 2α--0.5/α for two values and Θ(log α) for multiple values. In addition we improve the previous known lower and upper bounds of the Fixed Partition and Flexible Partition policies.For the FIFO preemptive model, we improve the general lower bound and show a tight bound for the special case of queue size 2. We prove that the bounded delay model with uniform delay 2 is equivalent to a modified FIFO preemptive model with queue size 2. We then give improved upper and lower bounds on the 2-uniform bounded delay model. We also give lower bound for the 2-variable bounded delay model, which matches the previously known upper bound.